Author: Felipe de Azevedo Piovezan Date: 2024-02-13T13:20:49-08:00 New Revision: 91f4a84a1504e718e4f4d4eef5db7713dc30a030
URL: https://github.com/llvm/llvm-project/commit/91f4a84a1504e718e4f4d4eef5db7713dc30a030 DIFF: https://github.com/llvm/llvm-project/commit/91f4a84a1504e718e4f4d4eef5db7713dc30a030.diff LOG: [lldb][DWARFIndex] Use IDX_parent to implement GetFullyQualifiedType query (#79932) This commit changes DebugNamesDWARFIndex so that it now overrides `GetFullyQualifiedType` and attempts to use DW_IDX_parent, when available, to speed up such queries. When this type of information is not available, the base-class implementation is used. With this commit, we now achieve the 4x speedups reported in [1]. [1]: https://discourse.llvm.org/t/rfc-improve-dwarf-5-debug-names-type-lookup-parsing-speed/74151/38 Added: lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp Modified: lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h lldb/unittests/SymbolFile/DWARF/CMakeLists.txt Removed: ################################################################################ diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h index a20a862d340296..7e6c5f51f4beb5 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h +++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h @@ -47,6 +47,10 @@ class DWARFDeclContext { DWARFDeclContext() : m_entries() {} + DWARFDeclContext(llvm::ArrayRef<Entry> entries) { + llvm::append_range(m_entries, entries); + } + void AppendDeclContext(dw_tag_t tag, const char *name) { m_entries.push_back(Entry(tag, name)); } diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp index b718f98340a70b..4da0d56fdcacb4 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp @@ -13,6 +13,7 @@ #include "lldb/Core/Module.h" #include "lldb/Utility/RegularExpression.h" #include "lldb/Utility/Stream.h" +#include "llvm/ADT/Sequence.h" #include <optional> using namespace lldb_private; @@ -218,6 +219,108 @@ void DebugNamesDWARFIndex::GetCompleteObjCClass( m_fallback.GetCompleteObjCClass(class_name, must_be_implementation, callback); } +namespace { +using Entry = llvm::DWARFDebugNames::Entry; + +/// If `entry` and all of its parents have an `IDX_parent`, use that information +/// to build and return a list of at most `max_parents` parent Entries. +/// `entry` itself is not included in the list. +/// If any parent does not have an `IDX_parent`, or the Entry data is corrupted, +/// nullopt is returned. +std::optional<llvm::SmallVector<Entry, 4>> +getParentChain(Entry entry, uint32_t max_parents) { + llvm::SmallVector<Entry, 4> parent_entries; + + do { + if (!entry.hasParentInformation()) + return std::nullopt; + + llvm::Expected<std::optional<Entry>> parent = entry.getParentDIEEntry(); + if (!parent) { + // Bad data. + LLDB_LOG_ERROR( + GetLog(DWARFLog::Lookups), parent.takeError(), + "Failed to extract parent entry from a non-empty IDX_parent"); + return std::nullopt; + } + + // Last parent in the chain. + if (!parent->has_value()) + break; + + parent_entries.push_back(**parent); + entry = **parent; + } while (parent_entries.size() < max_parents); + + return parent_entries; +} +} // namespace + +void DebugNamesDWARFIndex::GetFullyQualifiedType( + const DWARFDeclContext &context, + llvm::function_ref<bool(DWARFDIE die)> callback) { + if (context.GetSize() == 0) + return; + + llvm::StringRef leaf_name = context[0].name; + llvm::SmallVector<llvm::StringRef> parent_names; + for (auto idx : llvm::seq<int>(1, context.GetSize())) + parent_names.emplace_back(context[idx].name); + + // For each entry, grab its parent chain and check if we have a match. + for (const DebugNames::Entry &entry : + m_debug_names_up->equal_range(leaf_name)) { + if (!isType(entry.tag())) + continue; + + // Grab at most one extra parent, subsequent parents are not necessary to + // test equality. + std::optional<llvm::SmallVector<Entry, 4>> parent_chain = + getParentChain(entry, parent_names.size() + 1); + + if (!parent_chain) { + // Fallback: use the base class implementation. + if (!ProcessEntry(entry, [&](DWARFDIE die) { + return GetFullyQualifiedTypeImpl(context, die, callback); + })) + return; + continue; + } + + if (SameParentChain(parent_names, *parent_chain) && + !ProcessEntry(entry, callback)) + return; + } +} + +bool DebugNamesDWARFIndex::SameParentChain( + llvm::ArrayRef<llvm::StringRef> parent_names, + llvm::ArrayRef<DebugNames::Entry> parent_entries) const { + + if (parent_entries.size() != parent_names.size()) + return false; + + auto SameAsEntryATName = [this](llvm::StringRef name, + const DebugNames::Entry &entry) { + // Peek at the AT_name of `entry` and test equality to `name`. + auto maybe_dieoffset = entry.getDIEUnitOffset(); + if (!maybe_dieoffset) + return false; + auto die_ref = ToDIERef(entry); + if (!die_ref) + return false; + return name == m_debug_info.PeekDIEName(*die_ref); + }; + + // If the AT_name of any parent fails to match the expected name, we don't + // have a match. + for (auto [parent_name, parent_entry] : + llvm::zip_equal(parent_names, parent_entries)) + if (!SameAsEntryATName(parent_name, parent_entry)) + return false; + return true; +} + void DebugNamesDWARFIndex::GetTypes( ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) { for (const DebugNames::Entry &entry : diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h index cca0913c4124c9..b54dd1162d20ab 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h +++ b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h @@ -42,6 +42,11 @@ class DebugNamesDWARFIndex : public DWARFIndex { void GetCompleteObjCClass( ConstString class_name, bool must_be_implementation, llvm::function_ref<bool(DWARFDIE die)> callback) override; + + /// Uses DWARF5's IDX_parent fields, when available, to speed up this query. + void GetFullyQualifiedType( + const DWARFDeclContext &context, + llvm::function_ref<bool(DWARFDIE die)> callback) override; void GetTypes(ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) override; void GetTypes(const DWARFDeclContext &context, @@ -83,6 +88,10 @@ class DebugNamesDWARFIndex : public DWARFIndex { bool ProcessEntry(const DebugNames::Entry &entry, llvm::function_ref<bool(DWARFDIE die)> callback); + /// Returns true if `parent_entries` have identical names to `parent_names`. + bool SameParentChain(llvm::ArrayRef<llvm::StringRef> parent_names, + llvm::ArrayRef<DebugNames::Entry> parent_entries) const; + static void MaybeLogLookupError(llvm::Error error, const DebugNames::NameIndex &ni, llvm::StringRef name); diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h index 60baf694b463ec..01518b26ca669e 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h +++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h @@ -373,6 +373,9 @@ class SymbolFileDWARF : public SymbolFileCommon { Type *ResolveTypeUID(const DIERef &die_ref); + /// Returns the DWARFIndex for this symbol, if it exists. + DWARFIndex *getIndex() { return m_index.get(); } + protected: SymbolFileDWARF(const SymbolFileDWARF &) = delete; const SymbolFileDWARF &operator=(const SymbolFileDWARF &) = delete; diff --git a/lldb/unittests/SymbolFile/DWARF/CMakeLists.txt b/lldb/unittests/SymbolFile/DWARF/CMakeLists.txt index 4a37ece1242915..d5b0be7ea2a28c 100644 --- a/lldb/unittests/SymbolFile/DWARF/CMakeLists.txt +++ b/lldb/unittests/SymbolFile/DWARF/CMakeLists.txt @@ -1,5 +1,6 @@ add_lldb_unittest(SymbolFileDWARFTests DWARFASTParserClangTests.cpp + DWARFDebugNamesIndexTest.cpp DWARFDIETest.cpp DWARFIndexCachingTest.cpp DWARFUnitTest.cpp diff --git a/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp b/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp new file mode 100644 index 00000000000000..e56e628d68e8cf --- /dev/null +++ b/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp @@ -0,0 +1,208 @@ +//===-- DWARFDIETest.cpp ----------------------------------------------=---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Plugins/SymbolFile/DWARF/DWARFDIE.h" +#include "Plugins/SymbolFile/DWARF/DWARFDebugInfo.h" +#include "Plugins/SymbolFile/DWARF/DWARFDeclContext.h" +#include "Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h" +#include "TestingSupport/Symbol/YAMLModuleTester.h" +#include "llvm/ADT/STLExtras.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +using namespace lldb; +using namespace lldb_private; +using namespace lldb_private::plugin::dwarf; +using StringRef = llvm::StringRef; + +static void +check_num_matches(DebugNamesDWARFIndex &index, int expected_num_matches, + llvm::ArrayRef<DWARFDeclContext::Entry> ctx_entries) { + DWARFDeclContext ctx(ctx_entries); + int num_matches = 0; + + index.GetFullyQualifiedType(ctx, [&](DWARFDIE die) { + num_matches++; + return true; + }); + ASSERT_EQ(num_matches, expected_num_matches); +} + +static DWARFDeclContext::Entry make_entry(const char *c) { + return DWARFDeclContext::Entry(dwarf::DW_TAG_class_type, c); +} + +TEST(DWARFDebugNamesIndexTest, FullyQualifiedQueryWithIDXParent) { + const char *yamldata = R"( +--- !ELF +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + Type: ET_EXEC + Machine: EM_386 +DWARF: + debug_str: + - '1' + - '2' + - '3' + debug_abbrev: + - Table: + # We intentionally don't nest types in debug_info: if the nesting is not + # inferred from debug_names, we want the test to fail. + - Code: 0x1 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + - Code: 0x2 + Tag: DW_TAG_class_type + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + debug_info: + - Version: 4 + AddrSize: 8 + Entries: + - AbbrCode: 0x1 + - AbbrCode: 0x2 + Values: + - Value: 0x0 # Name "1" + - AbbrCode: 0x2 + Values: + - Value: 0x2 # Name "2" + - AbbrCode: 0x2 + Values: + - Value: 0x4 # Name "3" + - AbbrCode: 0x0 + debug_names: + Abbreviations: + - Code: 0x11 + Tag: DW_TAG_class_type + Indices: + - Idx: DW_IDX_parent + Form: DW_FORM_flag_present + - Idx: DW_IDX_die_offset + Form: DW_FORM_ref4 + - Code: 0x22 + Tag: DW_TAG_class_type + Indices: + - Idx: DW_IDX_parent + Form: DW_FORM_ref4 + - Idx: DW_IDX_die_offset + Form: DW_FORM_ref4 + Entries: + - Name: 0x0 # strp to Name1 + Code: 0x11 + Values: + - 0xc # Die offset to entry named "1" + - Name: 0x2 # strp to Name2 + Code: 0x22 + Values: + - 0x0 # Parent = First entry ("1") + - 0x11 # Die offset to entry named "1:2" + - Name: 0x4 # strp to Name3 + Code: 0x22 + Values: + - 0x6 # Parent = Second entry ("1::2") + - 0x16 # Die offset to entry named "1::2::3" + - Name: 0x4 # strp to Name3 + Code: 0x11 + Values: + - 0x16 # Die offset to entry named "3" +)"; + + YAMLModuleTester t(yamldata); + auto *symbol_file = + llvm::cast<SymbolFileDWARF>(t.GetModule()->GetSymbolFile()); + auto *index = static_cast<DebugNamesDWARFIndex *>(symbol_file->getIndex()); + ASSERT_NE(index, nullptr); + + check_num_matches(*index, 1, {make_entry("1")}); + check_num_matches(*index, 1, {make_entry("2"), make_entry("1")}); + check_num_matches(*index, 1, + {make_entry("3"), make_entry("2"), make_entry("1")}); + check_num_matches(*index, 0, {make_entry("2")}); + check_num_matches(*index, 1, {make_entry("3")}); +} + +TEST(DWARFDebugNamesIndexTest, FullyQualifiedQueryWithoutIDXParent) { + const char *yamldata = R"( +--- !ELF +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + Type: ET_EXEC + Machine: EM_386 +DWARF: + debug_str: + - '1' + - '2' + debug_abbrev: + - Table: + - Code: 0x1 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + - Code: 0x2 + Tag: DW_TAG_class_type + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x3 + Tag: DW_TAG_class_type + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + debug_info: + - Version: 4 + AddrSize: 8 + Entries: + - AbbrCode: 0x1 + - AbbrCode: 0x2 + Values: + - Value: 0x0 # Name "1" + - AbbrCode: 0x3 + Values: + - Value: 0x2 # Name "2" + - AbbrCode: 0x0 + - AbbrCode: 0x3 + Values: + - Value: 0x2 # Name "2" + - AbbrCode: 0x0 + debug_names: + Abbreviations: + - Code: 0x1 + Tag: DW_TAG_class_type + Indices: + - Idx: DW_IDX_die_offset + Form: DW_FORM_ref4 + Entries: + - Name: 0x0 # strp to Name1 + Code: 0x1 + Values: + - 0xc # Die offset to entry named "1" + - Name: 0x2 # strp to Name2 + Code: 0x1 + Values: + - 0x11 # Die offset to entry named "1::2" + - Name: 0x2 # strp to Name2 + Code: 0x1 + Values: + - 0x17 # Die offset to entry named "2" +)"; + + YAMLModuleTester t(yamldata); + auto *symbol_file = + llvm::cast<SymbolFileDWARF>(t.GetModule()->GetSymbolFile()); + auto *index = static_cast<DebugNamesDWARFIndex *>(symbol_file->getIndex()); + ASSERT_NE(index, nullptr); + + check_num_matches(*index, 1, {make_entry("1")}); + check_num_matches(*index, 1, {make_entry("2"), make_entry("1")}); + check_num_matches(*index, 1, {make_entry("2")}); +} _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits