LLVM  7.0.0svn
DWARFAcceleratorTable.cpp
Go to the documentation of this file.
1 //===- DWARFAcceleratorTable.cpp ------------------------------------------===//
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 
11 
12 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/Support/Compiler.h"
16 #include "llvm/Support/DJB.h"
17 #include "llvm/Support/Format.h"
20 #include <cstddef>
21 #include <cstdint>
22 #include <utility>
23 
24 using namespace llvm;
25 
26 namespace {
27 struct DwarfConstant {
28  StringRef (*StringFn)(unsigned);
30  unsigned Value;
31 };
32 
33 static raw_ostream &operator<<(raw_ostream &OS, const DwarfConstant &C) {
34  StringRef Str = C.StringFn(C.Value);
35  if (!Str.empty())
36  return OS << Str;
37  return OS << "DW_" << C.Type << "_Unknown_0x" << format("%x", C.Value);
38 }
39 } // namespace
40 
41 static DwarfConstant formatTag(unsigned Tag) {
42  return {dwarf::TagString, "TAG", Tag};
43 }
44 
45 static DwarfConstant formatForm(unsigned Form) {
46  return {dwarf::FormEncodingString, "FORM", Form};
47 }
48 
49 static DwarfConstant formatIndex(unsigned Idx) {
50  return {dwarf::IndexString, "IDX", Idx};
51 }
52 
53 static DwarfConstant formatAtom(unsigned Atom) {
54  return {dwarf::AtomTypeString, "ATOM", Atom};
55 }
56 
58 
60  uint32_t Offset = 0;
61 
62  // Check that we can at least read the header.
63  if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength)+4))
64  return make_error<StringError>("Section too small: cannot read header.",
66 
67  Hdr.Magic = AccelSection.getU32(&Offset);
68  Hdr.Version = AccelSection.getU16(&Offset);
69  Hdr.HashFunction = AccelSection.getU16(&Offset);
70  Hdr.BucketCount = AccelSection.getU32(&Offset);
71  Hdr.HashCount = AccelSection.getU32(&Offset);
72  Hdr.HeaderDataLength = AccelSection.getU32(&Offset);
73 
74  // Check that we can read all the hashes and offsets from the
75  // section (see SourceLevelDebugging.rst for the structure of the index).
76  // We need to substract one because we're checking for an *offset* which is
77  // equal to the size for an empty table and hence pointer after the section.
78  if (!AccelSection.isValidOffset(sizeof(Hdr) + Hdr.HeaderDataLength +
79  Hdr.BucketCount * 4 + Hdr.HashCount * 8 - 1))
80  return make_error<StringError>(
81  "Section too small: cannot read buckets and hashes.",
83 
84  HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);
85  uint32_t NumAtoms = AccelSection.getU32(&Offset);
86 
87  for (unsigned i = 0; i < NumAtoms; ++i) {
88  uint16_t AtomType = AccelSection.getU16(&Offset);
89  auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));
90  HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
91  }
92 
93  IsValid = true;
94  return Error::success();
95 }
96 
97 uint32_t AppleAcceleratorTable::getNumBuckets() { return Hdr.BucketCount; }
98 uint32_t AppleAcceleratorTable::getNumHashes() { return Hdr.HashCount; }
101  return Hdr.HeaderDataLength;
102 }
103 
104 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
107  return HdrData.Atoms;
108 }
109 
111  for (auto Atom : getAtomsDesc()) {
112  DWARFFormValue FormValue(Atom.second);
113  switch (Atom.first) {
117  if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) &&
118  !FormValue.isFormClass(DWARFFormValue::FC_Flag)) ||
119  FormValue.getForm() == dwarf::DW_FORM_sdata)
120  return false;
121  break;
122  default:
123  break;
124  }
125  }
126  return true;
127 }
128 
129 std::pair<uint32_t, dwarf::Tag>
132  dwarf::Tag DieTag = dwarf::DW_TAG_null;
133  DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
134 
135  for (auto Atom : getAtomsDesc()) {
136  DWARFFormValue FormValue(Atom.second);
137  FormValue.extractValue(AccelSection, &HashDataOffset, FormParams);
138  switch (Atom.first) {
140  DieOffset = *FormValue.getAsUnsignedConstant();
141  break;
143  DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
144  break;
145  default:
146  break;
147  }
148  }
149  return {DieOffset, DieTag};
150 }
151 
153  DictScope HeaderScope(W, "Header");
154  W.printHex("Magic", Magic);
155  W.printHex("Version", Version);
156  W.printHex("Hash function", HashFunction);
157  W.printNumber("Bucket count", BucketCount);
158  W.printNumber("Hashes count", HashCount);
159  W.printNumber("HeaderData length", HeaderDataLength);
160 }
161 
162 bool AppleAcceleratorTable::dumpName(ScopedPrinter &W,
164  uint32_t *DataOffset) const {
165  DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
166  uint32_t NameOffset = *DataOffset;
167  if (!AccelSection.isValidOffsetForDataOfSize(*DataOffset, 4)) {
168  W.printString("Incorrectly terminated list.");
169  return false;
170  }
171  unsigned StringOffset = AccelSection.getRelocatedValue(4, DataOffset);
172  if (!StringOffset)
173  return false; // End of list
174 
175  DictScope NameScope(W, ("Name@0x" + Twine::utohexstr(NameOffset)).str());
176  W.startLine() << format("String: 0x%08x", StringOffset);
177  W.getOStream() << " \"" << StringSection.getCStr(&StringOffset) << "\"\n";
178 
179  unsigned NumData = AccelSection.getU32(DataOffset);
180  for (unsigned Data = 0; Data < NumData; ++Data) {
181  ListScope DataScope(W, ("Data " + Twine(Data)).str());
182  unsigned i = 0;
183  for (auto &Atom : AtomForms) {
184  W.startLine() << format("Atom[%d]: ", i++);
185  if (Atom.extractValue(AccelSection, DataOffset, FormParams))
186  Atom.dump(W.getOStream());
187  else
188  W.getOStream() << "Error extracting the value";
189  W.getOStream() << "\n";
190  }
191  }
192  return true; // more entries follow
193 }
194 
196  if (!IsValid)
197  return;
198 
199  ScopedPrinter W(OS);
200 
201  Hdr.dump(W);
202 
203  W.printNumber("DIE offset base", HdrData.DIEOffsetBase);
204  W.printNumber("Number of atoms", uint64_t(HdrData.Atoms.size()));
206  {
207  ListScope AtomsScope(W, "Atoms");
208  unsigned i = 0;
209  for (const auto &Atom : HdrData.Atoms) {
210  DictScope AtomScope(W, ("Atom " + Twine(i++)).str());
211  W.startLine() << "Type: " << formatAtom(Atom.first) << '\n';
212  W.startLine() << "Form: " << formatForm(Atom.second) << '\n';
213  AtomForms.push_back(DWARFFormValue(Atom.second));
214  }
215  }
216 
217  // Now go through the actual tables and dump them.
218  uint32_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
219  unsigned HashesBase = Offset + Hdr.BucketCount * 4;
220  unsigned OffsetsBase = HashesBase + Hdr.HashCount * 4;
221 
222  for (unsigned Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket) {
223  unsigned Index = AccelSection.getU32(&Offset);
224 
225  ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
226  if (Index == UINT32_MAX) {
227  W.printString("EMPTY");
228  continue;
229  }
230 
231  for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
232  unsigned HashOffset = HashesBase + HashIdx*4;
233  unsigned OffsetsOffset = OffsetsBase + HashIdx*4;
234  uint32_t Hash = AccelSection.getU32(&HashOffset);
235 
236  if (Hash % Hdr.BucketCount != Bucket)
237  break;
238 
239  unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
240  ListScope HashScope(W, ("Hash 0x" + Twine::utohexstr(Hash)).str());
241  if (!AccelSection.isValidOffset(DataOffset)) {
242  W.printString("Invalid section offset");
243  continue;
244  }
245  while (dumpName(W, AtomForms, &DataOffset))
246  /*empty*/;
247  }
248  }
249 }
250 
251 AppleAcceleratorTable::Entry::Entry(
252  const AppleAcceleratorTable::HeaderData &HdrData)
253  : HdrData(&HdrData) {
254  Values.reserve(HdrData.Atoms.size());
255  for (const auto &Atom : HdrData.Atoms)
256  Values.push_back(DWARFFormValue(Atom.second));
257 }
258 
259 void AppleAcceleratorTable::Entry::extract(
261 
262  DWARFFormParams FormParams = {AccelTable.Hdr.Version, 0,
264  for (auto &Atom : Values)
265  Atom.extractValue(AccelTable.AccelSection, Offset, FormParams);
266 }
267 
269 AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType Atom) const {
270  assert(HdrData && "Dereferencing end iterator?");
271  assert(HdrData->Atoms.size() == Values.size());
272  for (const auto &Tuple : zip_first(HdrData->Atoms, Values)) {
273  if (std::get<0>(Tuple).first == Atom)
274  return std::get<1>(Tuple);
275  }
276  return None;
277 }
278 
281  return Off->getAsSectionOffset();
282  return None;
283 }
284 
287  return Off->getAsSectionOffset();
288  return None;
289 }
290 
293  if (!Tag)
294  return None;
296  return dwarf::Tag(*Value);
297  return None;
298 }
299 
301  const AppleAcceleratorTable &AccelTable, unsigned Offset)
302  : AccelTable(&AccelTable), Current(AccelTable.HdrData), DataOffset(Offset) {
303  if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
304  return;
305 
306  // Read the first entry.
307  NumData = AccelTable.AccelSection.getU32(&DataOffset);
308  Next();
309 }
310 
311 void AppleAcceleratorTable::ValueIterator::Next() {
312  assert(NumData > 0 && "attempted to increment iterator past the end");
313  auto &AccelSection = AccelTable->AccelSection;
314  if (Data >= NumData ||
315  !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
316  NumData = 0;
317  return;
318  }
319  Current.extract(*AccelTable, &DataOffset);
320  ++Data;
321 }
322 
325  if (!IsValid)
327 
328  // Find the bucket.
329  unsigned HashValue = djbHash(Key);
330  unsigned Bucket = HashValue % Hdr.BucketCount;
331  unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
332  unsigned HashesBase = BucketBase + Hdr.BucketCount * 4;
333  unsigned OffsetsBase = HashesBase + Hdr.HashCount * 4;
334 
335  unsigned BucketOffset = BucketBase + Bucket * 4;
336  unsigned Index = AccelSection.getU32(&BucketOffset);
337 
338  // Search through all hashes in the bucket.
339  for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
340  unsigned HashOffset = HashesBase + HashIdx * 4;
341  unsigned OffsetsOffset = OffsetsBase + HashIdx * 4;
342  uint32_t Hash = AccelSection.getU32(&HashOffset);
343 
344  if (Hash % Hdr.BucketCount != Bucket)
345  // We are already in the next bucket.
346  break;
347 
348  unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
349  unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset);
350  if (!StringOffset)
351  break;
352 
353  // Finally, compare the key.
354  if (Key == StringSection.getCStr(&StringOffset))
355  return make_range({*this, DataOffset}, ValueIterator());
356  }
358 }
359 
361  DictScope HeaderScope(W, "Header");
362  W.printHex("Length", UnitLength);
363  W.printNumber("Version", Version);
364  W.printHex("Padding", Padding);
365  W.printNumber("CU count", CompUnitCount);
366  W.printNumber("Local TU count", LocalTypeUnitCount);
367  W.printNumber("Foreign TU count", ForeignTypeUnitCount);
368  W.printNumber("Bucket count", BucketCount);
369  W.printNumber("Name count", NameCount);
370  W.printHex("Abbreviations table size", AbbrevTableSize);
371  W.startLine() << "Augmentation: '" << AugmentationString << "'\n";
372 }
373 
375  uint32_t *Offset) {
376  // Check that we can read the fixed-size part.
377  if (!AS.isValidOffset(*Offset + sizeof(HeaderPOD) - 1))
378  return make_error<StringError>("Section too small: cannot read header.",
380 
381  UnitLength = AS.getU32(Offset);
382  Version = AS.getU16(Offset);
383  Padding = AS.getU16(Offset);
384  CompUnitCount = AS.getU32(Offset);
385  LocalTypeUnitCount = AS.getU32(Offset);
386  ForeignTypeUnitCount = AS.getU32(Offset);
387  BucketCount = AS.getU32(Offset);
388  NameCount = AS.getU32(Offset);
389  AbbrevTableSize = AS.getU32(Offset);
390  AugmentationStringSize = AS.getU32(Offset);
391 
392  if (!AS.isValidOffsetForDataOfSize(*Offset, AugmentationStringSize))
393  return make_error<StringError>(
394  "Section too small: cannot read header augmentation.",
396  AugmentationString.resize(AugmentationStringSize);
397  AS.getU8(Offset, reinterpret_cast<uint8_t *>(AugmentationString.data()),
398  AugmentationStringSize);
399  *Offset = alignTo(*Offset, 4);
400  return Error::success();
401 }
402 
404  DictScope AbbrevScope(W, ("Abbreviation 0x" + Twine::utohexstr(Code)).str());
405  W.startLine() << "Tag: " << formatTag(Tag) << '\n';
406 
407  for (const auto &Attr : Attributes) {
408  W.startLine() << formatIndex(Attr.Index) << ": " << formatForm(Attr.Form)
409  << '\n';
410  }
411 }
412 
414  return {dwarf::Index(0), dwarf::Form(0)};
415 }
416 
418  return AE == sentinelAttrEnc();
419 }
420 
422  return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), {});
423 }
424 
425 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
426  return Abbr.Code == 0;
427 }
428 
429 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
430  return sentinelAbbrev();
431 }
432 
433 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
434  return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), {});
435 }
436 
438 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint32_t *Offset) {
439  if (*Offset >= EntriesBase) {
440  return make_error<StringError>("Incorrectly terminated abbreviation table.",
442  }
443 
444  uint32_t Index = Section.AccelSection.getULEB128(Offset);
445  uint32_t Form = Section.AccelSection.getULEB128(Offset);
446  return AttributeEncoding(dwarf::Index(Index), dwarf::Form(Form));
447 }
448 
450 DWARFDebugNames::NameIndex::extractAttributeEncodings(uint32_t *Offset) {
451  std::vector<AttributeEncoding> Result;
452  for (;;) {
453  auto AttrEncOr = extractAttributeEncoding(Offset);
454  if (!AttrEncOr)
455  return AttrEncOr.takeError();
456  if (isSentinel(*AttrEncOr))
457  return std::move(Result);
458 
459  Result.emplace_back(*AttrEncOr);
460  }
461 }
462 
464 DWARFDebugNames::NameIndex::extractAbbrev(uint32_t *Offset) {
465  if (*Offset >= EntriesBase) {
466  return make_error<StringError>("Incorrectly terminated abbreviation table.",
468  }
469 
470  uint32_t Code = Section.AccelSection.getULEB128(Offset);
471  if (Code == 0)
472  return sentinelAbbrev();
473 
474  uint32_t Tag = Section.AccelSection.getULEB128(Offset);
475  auto AttrEncOr = extractAttributeEncodings(Offset);
476  if (!AttrEncOr)
477  return AttrEncOr.takeError();
478  return Abbrev(Code, dwarf::Tag(Tag), std::move(*AttrEncOr));
479 }
480 
482  const DWARFDataExtractor &AS = Section.AccelSection;
483  uint32_t Offset = Base;
484  if (Error E = Hdr.extract(AS, &Offset))
485  return E;
486 
487  CUsBase = Offset;
488  Offset += Hdr.CompUnitCount * 4;
489  Offset += Hdr.LocalTypeUnitCount * 4;
490  Offset += Hdr.ForeignTypeUnitCount * 8;
491  BucketsBase = Offset;
492  Offset += Hdr.BucketCount * 4;
493  HashesBase = Offset;
494  if (Hdr.BucketCount > 0)
495  Offset += Hdr.NameCount * 4;
496  StringOffsetsBase = Offset;
497  Offset += Hdr.NameCount * 4;
498  EntryOffsetsBase = Offset;
499  Offset += Hdr.NameCount * 4;
500 
501  if (!AS.isValidOffsetForDataOfSize(Offset, Hdr.AbbrevTableSize))
502  return make_error<StringError>(
503  "Section too small: cannot read abbreviations.",
505 
506  EntriesBase = Offset + Hdr.AbbrevTableSize;
507 
508  for (;;) {
509  auto AbbrevOr = extractAbbrev(&Offset);
510  if (!AbbrevOr)
511  return AbbrevOr.takeError();
512  if (isSentinel(*AbbrevOr))
513  return Error::success();
514 
515  if (!Abbrevs.insert(std::move(*AbbrevOr)).second) {
516  return make_error<StringError>("Duplicate abbreviation code.",
518  }
519  }
520 }
521 DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
522  : NameIdx(&NameIdx), Abbr(&Abbr) {
523  // This merely creates form values. It is up to the caller
524  // (NameIndex::getEntry) to populate them.
525  Values.reserve(Abbr.Attributes.size());
526  for (const auto &Attr : Abbr.Attributes)
527  Values.emplace_back(Attr.Form);
528 }
529 
532  assert(Abbr->Attributes.size() == Values.size());
533  for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
534  if (std::get<0>(Tuple).Index == Index)
535  return std::get<1>(Tuple);
536  }
537  return None;
538 }
539 
541  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
542  return Off->getAsSectionOffset();
543  return None;
544 }
545 
546 Optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {
547  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
548  return Off->getAsUnsignedConstant();
549  return None;
550 }
551 
553  Optional<uint64_t> Index = getCUIndex();
554  if (!Index || *Index >= NameIdx->getCUCount())
555  return None;
556  return NameIdx->getCUOffset(*Index);
557 }
558 
560  W.printHex("Abbrev", Abbr->Code);
561  W.startLine() << "Tag: " << formatTag(Abbr->Tag) << "\n";
562 
563  assert(Abbr->Attributes.size() == Values.size());
564  for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
565  W.startLine() << formatIndex(std::get<0>(Tuple).Index) << ": ";
566  std::get<1>(Tuple).dump(W.getOStream());
567  W.getOStream() << '\n';
568  }
569 }
570 
572 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
573  return inconvertibleErrorCode();
574 }
575 
577  assert(CU < Hdr.CompUnitCount);
578  uint32_t Offset = CUsBase + 4 * CU;
579  return Section.AccelSection.getRelocatedValue(4, &Offset);
580 }
581 
583  assert(TU < Hdr.LocalTypeUnitCount);
584  uint32_t Offset = CUsBase + Hdr.CompUnitCount * 4;
585  return Section.AccelSection.getRelocatedValue(4, &Offset);
586 }
587 
589  assert(TU < Hdr.ForeignTypeUnitCount);
590  uint32_t Offset = CUsBase + (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) * 4;
591  return Section.AccelSection.getU64(&Offset);
592 }
593 
595 DWARFDebugNames::NameIndex::getEntry(uint32_t *Offset) const {
596  const DWARFDataExtractor &AS = Section.AccelSection;
597  if (!AS.isValidOffset(*Offset))
598  return make_error<StringError>("Incorrectly terminated entry list",
600 
601  uint32_t AbbrevCode = AS.getULEB128(Offset);
602  if (AbbrevCode == 0)
603  return make_error<SentinelError>();
604 
605  const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
606  if (AbbrevIt == Abbrevs.end())
607  return make_error<StringError>("Invalid abbreviation",
609 
610  Entry E(*this, *AbbrevIt);
611 
612  DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
613  for (auto &Value : E.Values) {
614  if (!Value.extractValue(AS, Offset, FormParams))
615  return make_error<StringError>("Error extracting index attribute values",
617  }
618  return std::move(E);
619 }
620 
621 DWARFDebugNames::NameTableEntry
622 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
623  assert(0 < Index && Index <= Hdr.NameCount);
624  uint32_t StringOffsetOffset = StringOffsetsBase + 4 * (Index - 1);
625  uint32_t EntryOffsetOffset = EntryOffsetsBase + 4 * (Index - 1);
626  const DWARFDataExtractor &AS = Section.AccelSection;
627 
628  uint32_t StringOffset = AS.getRelocatedValue(4, &StringOffsetOffset);
629  uint32_t EntryOffset = AS.getU32(&EntryOffsetOffset);
630  EntryOffset += EntriesBase;
631  return {StringOffset, EntryOffset};
632 }
633 
634 uint32_t
635 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
636  assert(Bucket < Hdr.BucketCount);
637  uint32_t BucketOffset = BucketsBase + 4 * Bucket;
638  return Section.AccelSection.getU32(&BucketOffset);
639 }
640 
641 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
642  assert(0 < Index && Index <= Hdr.NameCount);
643  uint32_t HashOffset = HashesBase + 4 * (Index - 1);
644  return Section.AccelSection.getU32(&HashOffset);
645 }
646 
647 // Returns true if we should continue scanning for entries, false if this is the
648 // last (sentinel) entry). In case of a parsing error we also return false, as
649 // it's not possible to recover this entry list (but the other lists may still
650 // parse OK).
651 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
652  uint32_t *Offset) const {
653  uint32_t EntryId = *Offset;
654  auto EntryOr = getEntry(Offset);
655  if (!EntryOr) {
656  handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
657  [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
658  return false;
659  }
660 
661  DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
662  EntryOr->dump(W);
663  return true;
664 }
665 
666 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W, uint32_t Index,
667  Optional<uint32_t> Hash) const {
668  const DataExtractor &SS = Section.StringSection;
669  NameTableEntry NTE = getNameTableEntry(Index);
670 
671  DictScope NameScope(W, ("Name " + Twine(Index)).str());
672  if (Hash)
673  W.printHex("Hash", *Hash);
674 
675  W.startLine() << format("String: 0x%08x", NTE.StringOffset);
676  W.getOStream() << " \"" << SS.getCStr(&NTE.StringOffset) << "\"\n";
677 
678  while (dumpEntry(W, &NTE.EntryOffset))
679  /*empty*/;
680 }
681 
682 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
683  ListScope CUScope(W, "Compilation Unit offsets");
684  for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
685  W.startLine() << format("CU[%u]: 0x%08x\n", CU, getCUOffset(CU));
686 }
687 
688 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
689  if (Hdr.LocalTypeUnitCount == 0)
690  return;
691 
692  ListScope TUScope(W, "Local Type Unit offsets");
693  for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
694  W.startLine() << format("LocalTU[%u]: 0x%08x\n", TU, getLocalTUOffset(TU));
695 }
696 
697 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
698  if (Hdr.ForeignTypeUnitCount == 0)
699  return;
700 
701  ListScope TUScope(W, "Foreign Type Unit signatures");
702  for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
703  W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
704  getForeignTUSignature(TU));
705  }
706 }
707 
708 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
709  ListScope AbbrevsScope(W, "Abbreviations");
710  for (const auto &Abbr : Abbrevs)
711  Abbr.dump(W);
712 }
713 
714 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
715  uint32_t Bucket) const {
716  ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
717  uint32_t Index = getBucketArrayEntry(Bucket);
718  if (Index == 0) {
719  W.printString("EMPTY");
720  return;
721  }
722  if (Index > Hdr.NameCount) {
723  W.printString("Name index is invalid");
724  return;
725  }
726 
727  for (; Index <= Hdr.NameCount; ++Index) {
728  uint32_t Hash = getHashArrayEntry(Index);
729  if (Hash % Hdr.BucketCount != Bucket)
730  break;
731 
732  dumpName(W, Index, Hash);
733  }
734 }
735 
737  DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
738  Hdr.dump(W);
739  dumpCUs(W);
740  dumpLocalTUs(W);
741  dumpForeignTUs(W);
742  dumpAbbreviations(W);
743 
744  if (Hdr.BucketCount > 0) {
745  for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
746  dumpBucket(W, Bucket);
747  return;
748  }
749 
750  W.startLine() << "Hash table not present\n";
751  for (uint32_t Index = 1; Index <= Hdr.NameCount; ++Index)
752  dumpName(W, Index, None);
753 }
754 
756  uint32_t Offset = 0;
757  while (AccelSection.isValidOffset(Offset)) {
758  NameIndex Next(*this, Offset);
759  if (llvm::Error E = Next.extract())
760  return E;
761  Offset = Next.getNextUnitOffset();
762  NameIndices.push_back(std::move(Next));
763  }
764  return Error::success();
765 }
766 
768  ScopedPrinter W(OS);
769  for (const NameIndex &NI : NameIndices)
770  NI.dump(W);
771 }
772 
774 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
775  const Header &Hdr = CurrentIndex->Hdr;
776  if (Hdr.BucketCount == 0) {
777  // No Hash Table, We need to search through all names in the Name Index.
778  for (uint32_t Index = 1; Index <= Hdr.NameCount; ++Index) {
779  NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
780  if (CurrentIndex->Section.StringSection.getCStr(&NTE.StringOffset) == Key)
781  return NTE.EntryOffset;
782  }
783  return None;
784  }
785 
786  // The Name Index has a Hash Table, so use that to speed up the search.
787  // Compute the Key Hash, if it has not been done already.
788  if (!Hash)
789  Hash = caseFoldingDjbHash(Key);
790  uint32_t Bucket = *Hash % Hdr.BucketCount;
791  uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
792  if (Index == 0)
793  return None; // Empty bucket
794 
795  for (; Index <= Hdr.NameCount; ++Index) {
796  uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
797  if (Hash % Hdr.BucketCount != Bucket)
798  return None; // End of bucket
799 
800  NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
801  if (CurrentIndex->Section.StringSection.getCStr(&NTE.StringOffset) == Key)
802  return NTE.EntryOffset;
803  }
804  return None;
805 }
806 
807 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
808  auto EntryOr = CurrentIndex->getEntry(&DataOffset);
809  if (!EntryOr) {
810  consumeError(EntryOr.takeError());
811  return false;
812  }
813  CurrentEntry = std::move(*EntryOr);
814  return true;
815 }
816 
817 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
818  Optional<uint32_t> Offset = findEntryOffsetInCurrentIndex();
819  if (!Offset)
820  return false;
821  DataOffset = *Offset;
822  return getEntryAtCurrentOffset();
823 }
824 
825 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
826  for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
827  CurrentIndex != End; ++CurrentIndex) {
828  if (findInCurrentIndex())
829  return;
830  }
831  setEnd();
832 }
833 
834 void DWARFDebugNames::ValueIterator::next() {
835  assert(CurrentIndex && "Incrementing an end() iterator?");
836 
837  // First try the next entry in the current Index.
838  if (getEntryAtCurrentOffset())
839  return;
840 
841  // Try the next Name Index.
842  ++CurrentIndex;
843  searchFromStartOfCurrentIndex();
844 }
845 
847  StringRef Key)
848  : CurrentIndex(AccelTable.NameIndices.begin()), Key(Key) {
849  searchFromStartOfCurrentIndex();
850 }
851 
854  if (NameIndices.empty())
856  return make_range(ValueIterator(*this, Key), ValueIterator());
857 }
uint64_t CallInst * C
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in the accelerator table matching Key.
static DwarfConstant formatTag(unsigned Tag)
StringRef IndexString(unsigned Idx)
Definition: Dwarf.cpp:561
void dump(ScopedPrinter &W) const
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:236
uint64_t getULEB128(uint32_t *offset_ptr) const
Extract a unsigned LEB128 value from *offset_ptr.
iterator_range< ValueIterator > equal_range(StringRef Key) const
Look up all entries in the accelerator table matching Key.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
StringRef AtomTypeString(unsigned Atom)
Definition: Dwarf.cpp:480
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
std::vector< AttributeEncoding > Attributes
List of index attributes.
void dump(ScopedPrinter &W) const
SmallVector< DWARFFormValue, 3 > Values
Optional< DWARFFormValue > lookup(dwarf::Index Index) const
Returns the value of the Index Attribute in this Accelerator Entry, if the Entry contains such Attrib...
static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc()
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:197
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:283
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:677
Optional< DWARFFormValue > lookup(HeaderData::AtomType Atom) const
Returns the value of the Atom in this Accelerator Entry, if the Entry contains such Atom...
uint16_t getU16(uint32_t *offset_ptr) const
Extract a uint16_t value from *offset_ptr.
bool isFormClass(FormClass FC) const
Base class for error info classes.
Definition: Error.h:47
Abbreviation describing the encoding of Name Index entries.
uint64_t getForeignTUSignature(uint32_t TU) const
Reads signature of foreign type unit TU. TU is 0-based.
dwarf::Form getForm() const
uint32_t getU32(uint32_t *offset_ptr) const
Extract a uint32_t value from *offset_ptr.
static DwarfConstant formatIndex(unsigned Idx)
Error extract(const DWARFDataExtractor &AS, uint32_t *Offset)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
ArrayRef< std::pair< HeaderData::AtomType, HeaderData::Form > > getAtomsDesc()
Return the Atom description, which can be used to interpret the raw values of the Accelerator Entries...
StringRef FormEncodingString(unsigned Encoding)
Definition: Dwarf.cpp:105
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::Error extract() override
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
Index attribute and its encoding.
static const uint16_t * lookup(unsigned opcode, unsigned domain, ArrayRef< uint16_t[3]> Table)
dwarf::Tag Tag
Dwarf Tag of the described entity.
Key
PAL metadata keys.
raw_ostream & getOStream()
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Represents a single accelerator table within the Dwarf 5 .debug_names section.
Optional< uint64_t > getCUOffset() const override
Returns the Offset of the Compilation Unit associated with this Accelerator Entry or None if the Comp...
static DWARFDebugNames::Abbrev sentinelAbbrev()
bool isValidOffsetForDataOfSize(uint32_t offset, uint32_t length) const
Test the availability of length bytes of data from offset.
DWARF v5-specific implementation of an Accelerator Entry.
This implements the Apple accelerator table format, a precursor of the DWARF 5 accelerator table form...
bool extractValue(const DWARFDataExtractor &Data, uint32_t *OffsetPtr, DWARFFormParams FormParams, const DWARFContext *Context=nullptr, const DWARFUnit *Unit=nullptr)
Extracts a value in Data at offset *OffsetPtr.
const uint32_t DW_INVALID_OFFSET
Identifier of an invalid DIE offset in the .debug_info section.
Definition: Dwarf.h:68
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
raw_ostream & startLine()
static const unsigned End
uint8_t getU8(uint32_t *offset_ptr) const
Extract a uint8_t value from *offset_ptr.
Optional< uint64_t > getAsUnsignedConstant() const
void printHex(StringRef Label, T Value)
Dwarf 5 Name Index header.
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&... args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest...
Definition: STLExtras.h:489
const AMDGPUAS & AS
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:962
uint32_t djbHash(StringRef Buffer, uint32_t H=5381)
The Bernstein hash function used by the DWARF accelerator tables.
Definition: DJB.cpp:26
uint32_t getLocalTUOffset(uint32_t TU) const
Reads offset of local type unit TU, TU is 0-based.
uint64_t getRelocatedValue(uint32_t Size, uint32_t *Off, uint64_t *SectionIndex=nullptr) const
Extracts a value and applies a relocation to the result if one exists for the given offset...
static const char *const Magic
Definition: Archive.cpp:42
A DataExtractor (typically for an in-memory copy of an object-file section) plus a relocation map for...
void printString(StringRef Value)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
.debug_names section consists of one or more units.
void handleAllErrors(Error E, HandlerTs &&... Handlers)
Behaves the same as handleErrors, except that it requires that all errors be handled by the given han...
Definition: Error.h:889
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
void printNumber(StringRef Label, uint64_t Value)
void dump(ScopedPrinter &W) const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
uint32_t caseFoldingDjbHash(StringRef Buffer, uint32_t H=5381)
Computes the Bernstein hash after folding the input according to the Dwarf 5 standard case folding ru...
Definition: DJB.cpp:81
void dump(raw_ostream &OS) const override
static Twine utohexstr(const uint64_t &Val)
Definition: Twine.h:385
A helper struct for DWARFFormValue methods, providing information that allows it to know the byte siz...
static DwarfConstant formatAtom(unsigned Atom)
A range adaptor for a pair of iterators.
This file contains constants used for implementing Dwarf debug support.
std::pair< uint32_t, dwarf::Tag > readAtoms(uint32_t &HashDataOffset)
Return information related to the DWARF DIE we&#39;re looking for when performing a lookup by name...
Optional< uint64_t > getDIEOffset() const override
Returns the Offset of the Debug Info Entry associated with this Accelerator Entry or None if the DIE ...
Optional< uint64_t > getCUOffset() const override
Returns the Offset of the Compilation Unit associated with this Accelerator Entry or None if the Comp...
StringRef TagString(unsigned Tag)
Definition: Dwarf.cpp:21
void dump(ScopedPrinter &W) const
const char * getCStr(uint32_t *offset_ptr) const
Extract a C string from *offset_ptr.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
bool isValidOffset(uint32_t offset) const
Test the validity of offset.
ValueIterator()=default
End marker.
void dump(raw_ostream &OS) const override
uint32_t Code
Abbreviation code.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static DwarfConstant formatForm(unsigned Form)
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
LLVM Value Representation.
Definition: Value.h:73
Optional< uint64_t > getDIEOffset() const override
Returns the Offset of the Debug Info Entry associated with this Accelerator Entry or None if the DIE ...
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
Optional< dwarf::Tag > getTag() const override
Returns the Tag of the Debug Info Entry associated with this Accelerator Entry or None if the Tag is ...
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
Marker as the end of a list of atoms.
Definition: Dwarf.h:365
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
uint32_t getCUOffset(uint32_t CU) const
Reads offset of compilation unit CU. CU is 0-based.
const uint64_t Version
Definition: InstrProf.h:867
std::error_code inconvertibleErrorCode()
The value returned by this function can be returned from convertToErrorCode for Error values where no...
Definition: Error.cpp:73