https://github.com/felipepiovezan updated https://github.com/llvm/llvm-project/pull/79932
>From ee09231ea101d97c1607552e161adcfe911a23f5 Mon Sep 17 00:00:00 2001 From: Felipe de Azevedo Piovezan <fpiove...@apple.com> Date: Mon, 29 Jan 2024 18:25:42 -0800 Subject: [PATCH 1/2] [lldb][DWARFIndex] Use IDX_parent to implement GetFullyQualifiedType query 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 --- .../SymbolFile/DWARF/DWARFDeclContext.h | 4 + .../SymbolFile/DWARF/DebugNamesDWARFIndex.cpp | 99 +++++++++ .../SymbolFile/DWARF/DebugNamesDWARFIndex.h | 9 + .../SymbolFile/DWARF/SymbolFileDWARF.h | 3 + .../unittests/SymbolFile/DWARF/CMakeLists.txt | 1 + .../DWARF/DWARFDebugNamesIndexTest.cpp | 210 ++++++++++++++++++ 6 files changed, 326 insertions(+) create mode 100644 lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h index a20a862d34029..7e6c5f51f4beb 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 b718f98340a70..6891d2fb6f610 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,104 @@ 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. +static 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. + consumeError(parent.takeError()); + 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; + + // Fallback: use the base class implementation. + auto fallback_impl = [&](const DebugNames::Entry &entry) { + return ProcessEntry(entry, [&](DWARFDIE die) { + return GetFullyQualifiedTypeImpl(context, die, callback); + }); + }; + + 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 (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. + auto parent_chain = getParentChain(entry, parent_names.size() + 1); + + if (!parent_chain) { + if (!fallback_impl(entry)) + 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) { + 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); + }; + + 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 cca0913c4124c..b54dd1162d20a 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 26a9502f90aa0..5778f5c887b57 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h +++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h @@ -360,6 +360,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 4a37ece124291..d5b0be7ea2a28 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 0000000000000..fb4160b5be412 --- /dev/null +++ b/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp @@ -0,0 +1,210 @@ +//===-- 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; + +void check_num_matches(DebugNamesDWARFIndex &index, int expected_num_matches, + llvm::ArrayRef<DWARFDeclContext::Entry> ctx_entries) { + DWARFDeclContext ctx(ctx_entries); + int num_matches = 0; + auto increment_matches = [&](DWARFDIE die) { + num_matches++; + return true; + }; + + index.GetFullyQualifiedType(ctx, increment_matches); + ASSERT_EQ(num_matches, expected_num_matches); +} + +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); + + auto make_entry = [](const char *c) { + return DWARFDeclContext::Entry(dwarf::DW_TAG_class_type, c); + }; + 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); + + auto make_entry = [](const char *c) { + return DWARFDeclContext::Entry(dwarf::DW_TAG_class_type, c); + }; + 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")}); +} >From 8a90b74c0dcefcc4404e21def61835691269251e Mon Sep 17 00:00:00 2001 From: Felipe de Azevedo Piovezan <fpiove...@apple.com> Date: Wed, 31 Jan 2024 10:11:24 -0800 Subject: [PATCH 2/2] fixup! review comments --- .../SymbolFile/DWARF/DebugNamesDWARFIndex.cpp | 26 ++++++++++--------- .../DWARF/DWARFDebugNamesIndexTest.cpp | 22 +++++++--------- 2 files changed, 24 insertions(+), 24 deletions(-) diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp index 6891d2fb6f610..6609676c9af07 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp @@ -227,7 +227,7 @@ using Entry = llvm::DWARFDebugNames::Entry; /// `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. -static std::optional<llvm::SmallVector<Entry, 4>> +std::optional<llvm::SmallVector<Entry, 4>> getParentChain(Entry entry, uint32_t max_parents) { llvm::SmallVector<Entry, 4> parent_entries; @@ -236,12 +236,13 @@ getParentChain(Entry entry, uint32_t max_parents) { return std::nullopt; llvm::Expected<std::optional<Entry>> parent = entry.getParentDIEEntry(); - if (!parent) { // Bad data. + if (!parent) { + // Bad data. consumeError(parent.takeError()); return std::nullopt; } - // Last parent in the chain + // Last parent in the chain. if (!parent->has_value()) break; @@ -259,18 +260,12 @@ void DebugNamesDWARFIndex::GetFullyQualifiedType( if (context.GetSize() == 0) return; - // Fallback: use the base class implementation. - auto fallback_impl = [&](const DebugNames::Entry &entry) { - return ProcessEntry(entry, [&](DWARFDIE die) { - return GetFullyQualifiedTypeImpl(context, die, callback); - }); - }; - 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())) @@ -278,10 +273,14 @@ void DebugNamesDWARFIndex::GetFullyQualifiedType( // Grab at most one extra parent, subsequent parents are not necessary to // test equality. - auto parent_chain = getParentChain(entry, parent_names.size() + 1); + std::optional<llvm::SmallVector<Entry, 4>> parent_chain = + getParentChain(entry, parent_names.size() + 1); if (!parent_chain) { - if (!fallback_impl(entry)) + // Fallback: use the base class implementation. + if (!ProcessEntry(entry, [&](DWARFDIE die) { + return GetFullyQualifiedTypeImpl(context, die, callback); + })) return; continue; } @@ -301,6 +300,7 @@ bool DebugNamesDWARFIndex::SameParentChain( 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; @@ -310,6 +310,8 @@ bool DebugNamesDWARFIndex::SameParentChain( 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)) diff --git a/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp b/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp index fb4160b5be412..e56e628d68e8c 100644 --- a/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp +++ b/lldb/unittests/SymbolFile/DWARF/DWARFDebugNamesIndexTest.cpp @@ -20,19 +20,23 @@ using namespace lldb_private; using namespace lldb_private::plugin::dwarf; using StringRef = llvm::StringRef; -void check_num_matches(DebugNamesDWARFIndex &index, int expected_num_matches, - llvm::ArrayRef<DWARFDeclContext::Entry> ctx_entries) { +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; - auto increment_matches = [&](DWARFDIE die) { + + index.GetFullyQualifiedType(ctx, [&](DWARFDIE die) { num_matches++; return true; - }; - - index.GetFullyQualifiedType(ctx, increment_matches); + }); 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 @@ -117,9 +121,6 @@ TEST(DWARFDebugNamesIndexTest, FullyQualifiedQueryWithIDXParent) { auto *index = static_cast<DebugNamesDWARFIndex *>(symbol_file->getIndex()); ASSERT_NE(index, nullptr); - auto make_entry = [](const char *c) { - return DWARFDeclContext::Entry(dwarf::DW_TAG_class_type, c); - }; check_num_matches(*index, 1, {make_entry("1")}); check_num_matches(*index, 1, {make_entry("2"), make_entry("1")}); check_num_matches(*index, 1, @@ -201,9 +202,6 @@ TEST(DWARFDebugNamesIndexTest, FullyQualifiedQueryWithoutIDXParent) { auto *index = static_cast<DebugNamesDWARFIndex *>(symbol_file->getIndex()); ASSERT_NE(index, nullptr); - auto make_entry = [](const char *c) { - return DWARFDeclContext::Entry(dwarf::DW_TAG_class_type, c); - }; 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
