llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-lldb Author: None (jeffreytan81) <details> <summary>Changes</summary> ## Summary This PR is a continuation of https://github.com/llvm/llvm-project/pull/108907 by using `.debug_names` parent chain faster lookup for namespaces. ## Implementation Similar to https://github.com/llvm/llvm-project/pull/108907. This PR adds a new API: `GetNamespacesWithParents` in `DWARFIndex` base class. The API performs the same function as `GetNamespaces()` with additional filtering using parents `CompilerDeclContext`. A default implementation is given in `DWARFIndex` class which parses debug info and performs the matching. In the `DebugNameDWARFIndex` override, parents `CompilerDeclContext` is cross checked with parent chain in `.debug_names` for much faster filtering before fallback to base implementation for final filtering. ## Performance Results For the same benchmark used in https://github.com/llvm/llvm-project/pull/108907, this PR improves: 48s => 28s --- Full diff: https://github.com/llvm/llvm-project/pull/110062.diff 5 Files Affected: - (modified) lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.cpp (+41) - (modified) lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.h (+23) - (modified) lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp (+164-1) - (modified) lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h (+36) - (modified) lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp (+4-3) ``````````diff diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.cpp index eafddbad03f57b..c6c5b8e8af1450 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.cpp @@ -126,3 +126,44 @@ bool DWARFIndex::GetFullyQualifiedTypeImpl( return callback(die); return true; } + +void DWARFIndex::GetTypesWithQuery( + TypeQuery &query, llvm::function_ref<bool(DWARFDIE die)> callback) { + GetTypes(query.GetTypeBasename(), [&](DWARFDIE die) { + return ProcessTypeDieMatchQuery(query, die, callback); + }); +} + +bool DWARFIndex::ProcessTypeDieMatchQuery( + TypeQuery &query, DWARFDIE die, + llvm::function_ref<bool(DWARFDIE die)> callback) { + // Nothing to match from query + if (query.GetContextRef().size() <= 1) + return callback(die); + + std::vector<lldb_private::CompilerContext> die_context; + if (query.GetModuleSearch()) + die_context = die.GetDeclContext(); + else + die_context = die.GetTypeLookupContext(); + + if (!query.ContextMatches(die_context)) + return true; + return callback(die); +} + +void DWARFIndex::GetNamespacesWithParents( + ConstString name, const CompilerDeclContext &parent_decl_ctx, + llvm::function_ref<bool(DWARFDIE die)> callback) { + GetNamespaces(name, [&](DWARFDIE die) { + return ProcessNamespaceDieMatchParents(parent_decl_ctx, die, callback); + }); +} + +bool DWARFIndex::ProcessNamespaceDieMatchParents( + const CompilerDeclContext &parent_decl_ctx, DWARFDIE die, + llvm::function_ref<bool(DWARFDIE die)> callback) { + if (!SymbolFileDWARF::DIEInDeclContext(parent_decl_ctx, die)) + return true; + return callback(die); +} diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.h index cb3ae8a06d7885..91f4a8d4713543 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.h +++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.h @@ -64,6 +64,21 @@ class DWARFIndex { virtual void GetNamespaces(ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) = 0; + /// Get type DIEs meeting requires of \a query. + /// in its decl parent chain as subset. A base implementation is provided, + /// Specializations should override this if they are able to provide a faster + /// implementation. + virtual void + GetTypesWithQuery(TypeQuery &query, + llvm::function_ref<bool(DWARFDIE die)> callback); + /// Get namespace DIEs whose base name match \param name with \param + /// parent_decl_ctx in its decl parent chain. A base implementation + /// is provided. Specializations should override this if they are able to + /// provide a faster implementation. + virtual void + GetNamespacesWithParents(ConstString name, + const CompilerDeclContext &parent_decl_ctx, + llvm::function_ref<bool(DWARFDIE die)> callback); virtual void GetFunctions(const Module::LookupInfo &lookup_info, SymbolFileDWARF &dwarf, const CompilerDeclContext &parent_decl_ctx, @@ -115,6 +130,14 @@ class DWARFIndex { bool GetFullyQualifiedTypeImpl(const DWARFDeclContext &context, DWARFDIE die, llvm::function_ref<bool(DWARFDIE die)> callback); + + /// Check if the type \a die can meet the requirements of \a query. + bool + ProcessTypeDieMatchQuery(TypeQuery &query, DWARFDIE die, + llvm::function_ref<bool(DWARFDIE die)> callback); + bool ProcessNamespaceDieMatchParents( + const CompilerDeclContext &parent_decl_ctx, DWARFDIE die, + llvm::function_ref<bool(DWARFDIE die)> callback); }; } // namespace dwarf } // namespace lldb_private::plugin diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp index 32d8a92305aafa..d22b5dbe7dee42 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp @@ -301,7 +301,8 @@ using Entry = llvm::DWARFDebugNames::Entry; /// 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) { +getParentChain(Entry entry, + uint32_t max_parents = std::numeric_limits<uint32_t>::max()) { llvm::SmallVector<Entry, 4> parent_entries; do { @@ -374,6 +375,21 @@ void DebugNamesDWARFIndex::GetFullyQualifiedType( m_fallback.GetFullyQualifiedType(context, callback); } +bool DebugNamesDWARFIndex::SameAsEntryContext( + const CompilerContext &query_context, + const DebugNames::Entry &entry) const { + // TODO: check dwarf tag matches. + // Peek at the AT_name of `entry` and test equality to `name`. + auto maybe_dieoffset = entry.getDIEUnitOffset(); + if (!maybe_dieoffset) + return false; + DWARFUnit *unit = GetNonSkeletonUnit(entry); + if (!unit) + return false; + return query_context.name == + unit->PeekDIEName(unit->GetOffset() + *maybe_dieoffset); +} + bool DebugNamesDWARFIndex::SameParentChain( llvm::ArrayRef<llvm::StringRef> parent_names, llvm::ArrayRef<DebugNames::Entry> parent_entries) const { @@ -402,6 +418,45 @@ bool DebugNamesDWARFIndex::SameParentChain( return true; } +bool DebugNamesDWARFIndex::SameParentChain( + llvm::ArrayRef<CompilerContext> parent_contexts, + llvm::ArrayRef<DebugNames::Entry> parent_entries) const { + if (parent_entries.size() != parent_contexts.size()) + return false; + + // If the AT_name of any parent fails to match the expected name, we don't + // have a match. + for (auto [parent_context, parent_entry] : + llvm::zip_equal(parent_contexts, parent_entries)) + if (!SameAsEntryContext(parent_context, parent_entry)) + return false; + return true; +} + +bool DebugNamesDWARFIndex::WithinParentChain( + llvm::ArrayRef<CompilerContext> query_contexts, + llvm::ArrayRef<DebugNames::Entry> parent_chain) const { + if (query_contexts.size() == parent_chain.size()) + return SameParentChain(query_contexts, parent_chain); + + // If parent chain does not have enough entries, we can't possibly have a + // match. + while (!query_contexts.empty() && + query_contexts.size() <= parent_chain.size()) { + if (SameAsEntryContext(query_contexts.front(), parent_chain.front())) { + query_contexts = query_contexts.drop_front(); + parent_chain = parent_chain.drop_front(); + } else { + // Name does not match, try next parent_chain entry if the current entry + // is namespace because the current one can be an inline namespace. + if (parent_chain.front().tag() != DW_TAG_namespace) + return false; + parent_chain = parent_chain.drop_front(); + } + } + return query_contexts.empty(); +} + void DebugNamesDWARFIndex::GetTypes( ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) { for (const DebugNames::Entry &entry : @@ -444,6 +499,114 @@ void DebugNamesDWARFIndex::GetNamespaces( m_fallback.GetNamespaces(name, callback); } +llvm::SmallVector<CompilerContext> +DebugNamesDWARFIndex::GetTypeQueryParentContexts(TypeQuery &query) { + std::vector<lldb_private::CompilerContext> &query_decl_context = + query.GetContextRef(); + llvm::SmallVector<CompilerContext> parent_contexts; + if (!query_decl_context.empty()) { + // Skip the last entry, it is the type we are looking for. + // Reverse the query decl context to match parent chain. + llvm::ArrayRef<CompilerContext> parent_contexts_ref( + query_decl_context.data(), query_decl_context.size() - 1); + for (const CompilerContext &ctx : llvm::reverse(parent_contexts_ref)) { + // Skip any context without name because .debug_names might not encode + // them. (e.g. annonymous namespace) + if ((ctx.kind & CompilerContextKind::AnyType) != + CompilerContextKind::Invalid && + !ctx.name.IsEmpty()) + parent_contexts.push_back(ctx); + } + } + return parent_contexts; +} + +void DebugNamesDWARFIndex::GetTypesWithQuery( + TypeQuery &query, llvm::function_ref<bool(DWARFDIE die)> callback) { + ConstString name = query.GetTypeBasename(); + std::vector<lldb_private::CompilerContext> query_context = + query.GetContextRef(); + if (query_context.size() <= 1) + return GetTypes(name, callback); + + llvm::SmallVector<CompilerContext> parent_contexts = + GetTypeQueryParentContexts(query); + // 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(name)) { + if (!isType(entry.tag())) + continue; + + // If we get a NULL foreign_tu back, the entry doesn't match the type unit + // in the .dwp file, or we were not able to load the .dwo file or the DWO ID + // didn't match. + std::optional<DWARFTypeUnit *> foreign_tu = GetForeignTypeUnit(entry); + if (foreign_tu && foreign_tu.value() == nullptr) + continue; + + std::optional<llvm::SmallVector<Entry, 4>> parent_chain = + getParentChain(entry); + if (!parent_chain) { + // Fallback: use the base class implementation. + if (!ProcessEntry(entry, [&](DWARFDIE die) { + return ProcessTypeDieMatchQuery(query, die, callback); + })) + return; + continue; + } + + if (WithinParentChain(parent_contexts, *parent_chain) && + !ProcessEntry(entry, [&](DWARFDIE die) { + // After .debug_names filtering still sending to base class for + // further filtering before calling the callback. + return ProcessTypeDieMatchQuery(query, die, callback); + })) + return; + } + m_fallback.GetTypesWithQuery(query, callback); +} + +void DebugNamesDWARFIndex::GetNamespacesWithParents( + ConstString name, const CompilerDeclContext &parent_decl_ctx, + llvm::function_ref<bool(DWARFDIE die)> callback) { + std::vector<lldb_private::CompilerContext> parent_contexts = + parent_decl_ctx.GetCompilerContext(); + if (parent_contexts.empty()) + return GetNamespaces(name, callback); + + llvm::SmallVector<CompilerContext> parent_named_contexts; + std::copy_if(parent_contexts.rbegin(), parent_contexts.rend(), + std::back_inserter(parent_named_contexts), + [](const CompilerContext &ctx) { return !ctx.name.IsEmpty(); }); + for (const DebugNames::Entry &entry : + m_debug_names_up->equal_range(name.GetStringRef())) { + lldb_private::dwarf::Tag entry_tag = entry.tag(); + if (entry_tag == DW_TAG_namespace || + entry_tag == DW_TAG_imported_declaration) { + std::optional<llvm::SmallVector<Entry, 4>> parent_chain = + getParentChain(entry); + if (!parent_chain) { + // Fallback: use the base class implementation. + if (!ProcessEntry(entry, [&](DWARFDIE die) { + return ProcessNamespaceDieMatchParents(parent_decl_ctx, die, + callback); + })) + return; + continue; + } + + if (WithinParentChain(parent_named_contexts, *parent_chain) && + !ProcessEntry(entry, [&](DWARFDIE die) { + // After .debug_names filtering still sending to base class for + // further filtering before calling the callback. + return ProcessNamespaceDieMatchParents(parent_decl_ctx, die, + callback); + })) + return; + } + } + m_fallback.GetNamespacesWithParents(name, parent_decl_ctx, callback); +} + void DebugNamesDWARFIndex::GetFunctions( const Module::LookupInfo &lookup_info, SymbolFileDWARF &dwarf, const CompilerDeclContext &parent_decl_ctx, diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h index cb15c1d4f994b3..d2f3186fd9118a 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h +++ b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h @@ -52,6 +52,12 @@ class DebugNamesDWARFIndex : public DWARFIndex { llvm::function_ref<bool(DWARFDIE die)> callback) override; void GetNamespaces(ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) override; + void + GetTypesWithQuery(TypeQuery &query, + llvm::function_ref<bool(DWARFDIE die)> callback) override; + void GetNamespacesWithParents( + ConstString name, const CompilerDeclContext &parent_decl_ctx, + llvm::function_ref<bool(DWARFDIE die)> callback) override; void GetFunctions(const Module::LookupInfo &lookup_info, SymbolFileDWARF &dwarf, const CompilerDeclContext &parent_decl_ctx, @@ -118,6 +124,36 @@ class DebugNamesDWARFIndex : public DWARFIndex { bool SameParentChain(llvm::ArrayRef<llvm::StringRef> parent_names, llvm::ArrayRef<DebugNames::Entry> parent_entries) const; + bool SameParentChain(llvm::ArrayRef<CompilerContext> parent_names, + llvm::ArrayRef<DebugNames::Entry> parent_entries) const; + + /// Returns true if \a parent_contexts entries are within \a parent_chain. + /// This is diffferent from SameParentChain() which checks for exact match. + /// This function is required because \a parent_chain can contain inline + /// namespace entries which may not be specified in \a parent_contexts by + /// client. + /// + /// \param[in] parent_contexts + /// The list of parent contexts to check for. + /// + /// \param[in] parent_chain + /// The fully qualified parent chain entries from .debug_names index table + /// to check against. + /// + /// \returns + /// True if all \a parent_contexts entries are can be sequentially found + /// inside + /// \a parent_chain, otherwise False. + bool WithinParentChain(llvm::ArrayRef<CompilerContext> parent_contexts, + llvm::ArrayRef<DebugNames::Entry> parent_chain) const; + + /// Returns true if .debug_names pool entry \p entry matches \p query_context. + bool SameAsEntryContext(const CompilerContext &query_context, + const DebugNames::Entry &entry) const; + + llvm::SmallVector<CompilerContext> + GetTypeQueryParentContexts(TypeQuery &query); + static void MaybeLogLookupError(llvm::Error error, const DebugNames::NameIndex &ni, llvm::StringRef name); diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp index f721ca00fd3559..f1f2b8663c43a1 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp @@ -2748,8 +2748,9 @@ void SymbolFileDWARF::FindTypes(const TypeQuery &query, TypeResults &results) { std::lock_guard<std::recursive_mutex> guard(GetModuleMutex()); + TypeQuery query_full(query); bool have_index_match = false; - m_index->GetTypes(type_basename, [&](DWARFDIE die) { + m_index->GetTypesWithQuery(query_full, [&](DWARFDIE die) { // Check the language, but only if we have a language filter. if (query.HasLanguage()) { if (!query.LanguageMatches(GetLanguageFamily(*die.GetCU()))) @@ -2813,7 +2814,7 @@ void SymbolFileDWARF::FindTypes(const TypeQuery &query, TypeResults &results) { auto type_basename_simple = query_simple.GetTypeBasename(); // Copy our match's context and update the basename we are looking for // so we can use this only to compare the context correctly. - m_index->GetTypes(type_basename_simple, [&](DWARFDIE die) { + m_index->GetTypesWithQuery(query_simple, [&](DWARFDIE die) { // Check the language, but only if we have a language filter. if (query.HasLanguage()) { if (!query.LanguageMatches(GetLanguageFamily(*die.GetCU()))) @@ -2898,7 +2899,7 @@ SymbolFileDWARF::FindNamespace(ConstString name, if (!DeclContextMatchesThisSymbolFile(parent_decl_ctx)) return namespace_decl_ctx; - m_index->GetNamespaces(name, [&](DWARFDIE die) { + m_index->GetNamespacesWithParents(name, parent_decl_ctx, [&](DWARFDIE die) { if (!DIEInDeclContext(parent_decl_ctx, die, only_root_namespaces)) return true; // The containing decl contexts don't match `````````` </details> https://github.com/llvm/llvm-project/pull/110062 _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
