Index: llvm/trunk/include/llvm/BinaryFormat/Dwarf.h =================================================================== --- llvm/trunk/include/llvm/BinaryFormat/Dwarf.h +++ llvm/trunk/include/llvm/BinaryFormat/Dwarf.h @@ -491,6 +491,9 @@ /// Constants that define the DWARF format as 32 or 64 bit. enum DwarfFormat : uint8_t { DWARF32, DWARF64 }; +/// The Bernstein hash function used by the accelerator tables. +uint32_t djbHash(StringRef Buffer); + } // End of namespace dwarf } // End of namespace llvm Index: llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h +++ llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h @@ -13,7 +13,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/BinaryFormat/Dwarf.h" #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h" -#include "llvm/DebugInfo/DWARF/DWARFRelocMap.h" +#include "llvm/DebugInfo/DWARF/DWARFFormValue.h" #include #include @@ -21,6 +21,9 @@ class raw_ostream; +/// This implements the Apple accelerator table format, a precursor of the +/// DWARF 5 accelerator table format. +/// TODO: Factor out a common base class for both formats. class DWARFAcceleratorTable { struct Header { uint32_t Magic; @@ -43,8 +46,46 @@ struct HeaderData HdrData; DWARFDataExtractor AccelSection; DataExtractor StringSection; + bool IsValid = false; public: + /// An iterator for the entries associated with one key. Each entry can have + /// multiple DWARFFormValues. + class ValueIterator : public std::iterator> { + const DWARFAcceleratorTable *AccelTable = nullptr; + SmallVector AtomForms; ///< The decoded data entry. + + unsigned DataOffset = 0; ///< Offset into the section. + unsigned Data = 0; ///< Current data entry. + unsigned NumData = 0; ///< Number of data entries. + + /// Advance the iterator. + void Next(); + public: + /// Construct a new iterator for the entries at \p DataOffset. + ValueIterator(const DWARFAcceleratorTable &AccelTable, unsigned DataOffset); + /// End marker. + ValueIterator() : NumData(0) {} + + const ArrayRef operator*() const { + return AtomForms; + } + ValueIterator &operator++() { Next(); return *this; } + ValueIterator operator++(int) { + ValueIterator I(*this); + Next(); + return I; + } + friend bool operator==(const ValueIterator &A, const ValueIterator &B) { + return A.NumData == B.NumData && A.DataOffset == B.DataOffset; + } + friend bool operator!=(const ValueIterator &A, const ValueIterator &B) { + return !(A == B); + } + }; + + DWARFAcceleratorTable(const DWARFDataExtractor &AccelSection, DataExtractor StringSection) : AccelSection(AccelSection), StringSection(StringSection) {} @@ -67,6 +108,9 @@ /// DieTag is the tag of the DIE std::pair readAtoms(uint32_t &HashDataOffset); void dump(raw_ostream &OS) const; + + /// Look up all entries in the accelerator table matching \c Key. + iterator_range equal_range(StringRef Key) const; }; } // end namespace llvm Index: llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFContext.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFContext.h +++ llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFContext.h @@ -17,6 +17,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/ADT/iterator_range.h" #include "llvm/DebugInfo/DIContext.h" +#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h" #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h" #include "llvm/DebugInfo/DWARF/DWARFDebugAbbrev.h" #include "llvm/DebugInfo/DWARF/DWARFDebugAranges.h" @@ -68,6 +69,7 @@ std::unique_ptr DebugFrame; std::unique_ptr EHFrame; std::unique_ptr Macro; + std::unique_ptr AppleNames; DWARFUnitSection DWOCUs; std::deque> DWOTUs; @@ -237,6 +239,9 @@ /// Get a pointer to the parsed DebugMacro object. const DWARFDebugMacro *getDebugMacro(); + /// Get a reference to the parsed accelerator table object. + const DWARFAcceleratorTable &getAppleNames(); + /// Get a pointer to a parsed line table corresponding to a compile unit. const DWARFDebugLine::LineTable *getLineTableForUnit(DWARFUnit *cu); Index: llvm/trunk/lib/BinaryFormat/Dwarf.cpp =================================================================== --- llvm/trunk/lib/BinaryFormat/Dwarf.cpp +++ llvm/trunk/lib/BinaryFormat/Dwarf.cpp @@ -575,3 +575,10 @@ } return ExtensionsOk; } + +uint32_t llvm::dwarf::djbHash(StringRef Buffer) { + uint32_t H = 5381; + for (char C : Buffer.bytes()) + H = ((H << 5) + H) + C; + return H; +} Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h @@ -68,13 +68,6 @@ class DwarfDebug; class DwarfAccelTable { - static uint32_t HashDJB(StringRef Str) { - uint32_t h = 5381; - for (unsigned i = 0, e = Str.size(); i != e; ++i) - h = ((h << 5) + h) + Str[i]; - return h; - } - // Helper function to compute the number of buckets needed based on // the number of unique hashes. void ComputeBucketCount(); @@ -199,7 +192,7 @@ HashData(StringRef S, DwarfAccelTable::DataArray &Data) : Str(S), Data(Data) { - HashValue = DwarfAccelTable::HashDJB(S); + HashValue = dwarf::djbHash(S); } #ifndef NDEBUG Index: llvm/trunk/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp +++ llvm/trunk/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp @@ -12,7 +12,6 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/BinaryFormat/Dwarf.h" #include "llvm/DebugInfo/DWARF/DWARFContext.h" -#include "llvm/DebugInfo/DWARF/DWARFFormValue.h" #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Format.h" @@ -52,6 +51,7 @@ HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm)); } + IsValid = true; return true; } @@ -109,6 +109,9 @@ } LLVM_DUMP_METHOD void DWARFAcceleratorTable::dump(raw_ostream &OS) const { + if (!IsValid) + return; + // Dump the header. OS << "Magic = " << format("0x%08x", Hdr.Magic) << '\n' << "Version = " << format("0x%04x", Hdr.Version) << '\n' @@ -190,3 +193,67 @@ } } } + +DWARFAcceleratorTable::ValueIterator::ValueIterator( + const DWARFAcceleratorTable &AccelTable, unsigned Offset) + : AccelTable(&AccelTable), DataOffset(Offset) { + if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) + return; + + for (const auto &Atom : AccelTable.HdrData.Atoms) + AtomForms.push_back(DWARFFormValue(Atom.second)); + + // Read the first entry. + NumData = AccelTable.AccelSection.getU32(&DataOffset); + Next(); +} + +void DWARFAcceleratorTable::ValueIterator::Next() { + assert(NumData > 0 && "attempted to increment iterator past the end"); + auto &AccelSection = AccelTable->AccelSection; + if (Data >= NumData || + !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) { + NumData = 0; + return; + } + for (auto &Atom : AtomForms) + Atom.extractValue(AccelSection, &DataOffset, nullptr); + ++Data; +} + +iterator_range +DWARFAcceleratorTable::equal_range(StringRef Key) const { + if (!IsValid) + return make_range(ValueIterator(), ValueIterator()); + + // Find the bucket. + unsigned HashValue = dwarf::djbHash(Key); + unsigned Bucket = HashValue % Hdr.NumBuckets; + unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength; + unsigned HashesBase = BucketBase + Hdr.NumBuckets * 4; + unsigned OffsetsBase = HashesBase + Hdr.NumHashes * 4; + + unsigned BucketOffset = BucketBase + Bucket * 4; + unsigned Index = AccelSection.getU32(&BucketOffset); + + // Search through all hashes in the bucket. + for (unsigned HashIdx = Index; HashIdx < Hdr.NumHashes; ++HashIdx) { + unsigned HashOffset = HashesBase + HashIdx * 4; + unsigned OffsetsOffset = OffsetsBase + HashIdx * 4; + uint32_t Hash = AccelSection.getU32(&HashOffset); + + if (Hash % Hdr.NumBuckets != Bucket) + // We are already in the next bucket. + break; + + unsigned DataOffset = AccelSection.getU32(&OffsetsOffset); + unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset); + if (!StringOffset) + break; + + // Finally, compare the key. + if (Key == StringSection.getCStr(&StringOffset)) + return make_range({*this, DataOffset}, ValueIterator()); + } + return make_range(ValueIterator(), ValueIterator()); +} Index: llvm/trunk/lib/DebugInfo/DWARF/DWARFContext.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/DWARF/DWARFContext.cpp +++ llvm/trunk/lib/DebugInfo/DWARF/DWARFContext.cpp @@ -453,8 +453,7 @@ if (shouldDump(Explicit, ".apple_names", DIDT_ID_AppleNames, DObj->getAppleNamesSection().Data)) - dumpAccelSection(OS, *DObj, DObj->getAppleNamesSection(), - DObj->getStringSection(), isLittleEndian()); + getAppleNames().dump(OS); if (shouldDump(Explicit, ".apple_types", DIDT_ID_AppleTypes, DObj->getAppleTypesSection().Data)) @@ -638,6 +637,24 @@ return Macro.get(); } +static DWARFAcceleratorTable & +getAccelTable(std::unique_ptr &Cache, + const DWARFObject &Obj, const DWARFSection &Section, + StringRef StringSection, bool IsLittleEndian) { + if (Cache) + return *Cache; + DWARFDataExtractor AccelSection(Obj, Section, IsLittleEndian, 0); + DataExtractor StrData(StringSection, IsLittleEndian, 0); + Cache.reset(new DWARFAcceleratorTable(AccelSection, StrData)); + Cache->extract(); + return *Cache; +} + +const DWARFAcceleratorTable &DWARFContext::getAppleNames() { + return getAccelTable(AppleNames, *DObj, DObj->getAppleNamesSection(), + DObj->getStringSection(), isLittleEndian()); +} + const DWARFLineTable * DWARFContext::getLineTableForUnit(DWARFUnit *U) { if (!Line) Index: llvm/trunk/test/tools/llvm-dwarfdump/X86/find.test =================================================================== --- llvm/trunk/test/tools/llvm-dwarfdump/X86/find.test +++ llvm/trunk/test/tools/llvm-dwarfdump/X86/find.test @@ -0,0 +1,28 @@ +RUN: llvm-mc %S/brief.s -filetype obj -triple x86_64-apple-darwin -o - \ +RUN: | llvm-dwarfdump -find=not_there_at_all - | \ +RUN: FileCheck %s --check-prefix=EMPTY --allow-empty +EMPTY: {{^$}} + +RUN: llvm-mc %S/brief.s -filetype obj -triple x86_64-apple-darwin -o - \ +RUN: | llvm-dwarfdump -find=main - | FileCheck %s +CHECK: .debug_info contents: +CHECK-NOT: {{:}} +CHECK: : DW_TAG_subprogram +CHECK-NOT: {{:}} +CHECK: DW_AT_name ("main") +CHECK-NOT: {{:}} + +RUN: llvm-dwarfdump --debug-info %S/../../dsymutil/Inputs/libfat-test.a \ +RUN: -find=x86_64h_var -find=i386_var \ +RUN: | FileCheck %s --check-prefix=MULTI +MULTI: .debug_info contents: +MULTI-NOT: {{: DW}} +MULTI: : DW_TAG_variable +MULTI-NOT: {{: DW}} +MULTI: DW_AT_name ("i386_var") +MULTI-NOT: {{: DW}} +MULTI: .debug_info contents: +MULTI: : DW_TAG_variable +MULTI-NOT: {{: DW}} +MULTI: DW_AT_name ("x86_64h_var") +MULTI-NOT: {{: DW}} Index: llvm/trunk/test/tools/llvm-dwarfdump/cmdline.test =================================================================== --- llvm/trunk/test/tools/llvm-dwarfdump/cmdline.test +++ llvm/trunk/test/tools/llvm-dwarfdump/cmdline.test @@ -6,6 +6,7 @@ HELP: -debug-info - Dump the .debug_info section HELP: -eh-frame HELP: Specific Options +HELP: -find HELP: -recurse-depth= HELP: -show-children HELP: -show-parents Index: llvm/trunk/tools/llvm-dwarfdump/llvm-dwarfdump.cpp =================================================================== --- llvm/trunk/tools/llvm-dwarfdump/llvm-dwarfdump.cpp +++ llvm/trunk/tools/llvm-dwarfdump/llvm-dwarfdump.cpp @@ -134,6 +134,13 @@ "name or by number. This option can be specified " "multiple times, once for each desired architecture."), cat(DwarfDumpCategory)); +static list + Find("find", + desc("Search for the exact match for in the accelerator tables " + "and print the matching debug information entries."), + value_desc("name"), cat(DwarfDumpCategory)); +static alias FindAlias("f", desc("Alias for -find"), aliasopt(Find)); + static opt DumpUUID("uuid", desc("Show the UUID for each architecture"), cat(DwarfDumpCategory)); static alias DumpUUIDAlias("u", desc("Alias for -uuid"), aliasopt(DumpUUID)); @@ -164,7 +171,7 @@ cat(DwarfDumpCategory), init(-1U), value_desc("N")); static alias RecurseDepthAlias("r", desc("Alias for -recurse-depth"), aliasopt(RecurseDepth)); - + static opt SummarizeTypes("summarize-types", desc("Abbreviate the description of type unit entries"), @@ -236,6 +243,22 @@ raw_ostream &OS) { logAllUnhandledErrors(DICtx.loadRegisterInfo(Obj), errs(), Filename.str() + ": "); + + // Handle the --find option and lower it to --debug-info=. + if (!Find.empty()) { + DumpOffsets[DIDT_ID_DebugInfo] = [&]() -> Optional { + for (auto Name : Find) + for (auto Entry : DICtx.getAppleNames().equal_range(Name)) + for (auto Atom : Entry) + if (auto Offset = Atom.getAsSectionOffset()) + return DumpOffsets[DIDT_ID_DebugInfo] = *Offset; + return None; + }(); + // Early exit if --find was specified but the current file doesn't have it. + if (!DumpOffsets[DIDT_ID_DebugInfo]) + return true; + } + // The UUID dump already contains all the same information. if (!(DumpType & DIDT_UUID) || DumpType == DIDT_All) OS << Filename << ":\tfile format " << Obj.getFileFormatName() << '\n';