aprantl created this revision.
aprantl added a reviewer: teemperor.
Herald added a reviewer: jdoerfert.
Herald added a reviewer: shafik.
I wanted to further simplify ParseTypeFromClangModule by replacing the
hand-rolled loop with ForEachExternalModule, and then realized that
ForEachExternalModule also had the problem of visiting the same leaf node an
exponential number of times in the worst-case. This adds a set of
`searched_symbol_files` set to the function as well as the ability to
early-exit from it.
https://reviews.llvm.org/D70215
Files:
lldb/include/lldb/Symbol/CompileUnit.h
lldb/include/lldb/Symbol/SymbolFile.h
lldb/source/Plugins/ExpressionParser/Clang/ClangUserExpression.cpp
lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp
lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.h
lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp
lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp
lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
lldb/source/Symbol/CompileUnit.cpp
Index: lldb/source/Symbol/CompileUnit.cpp
===================================================================
--- lldb/source/Symbol/CompileUnit.cpp
+++ lldb/source/Symbol/CompileUnit.cpp
@@ -379,9 +379,12 @@
return m_imported_modules;
}
-void CompileUnit::ForEachExternalModule(llvm::function_ref<void(ModuleSP)> f) {
+bool CompileUnit::ForEachExternalModule(
+ llvm::DenseSet<SymbolFile *> &visited_symbol_files,
+ llvm::function_ref<bool(Module &)> lambda) {
if (SymbolFile *symfile = GetModule()->GetSymbolFile())
- symfile->ForEachExternalModule(*this, f);
+ return symfile->ForEachExternalModule(*this, visited_symbol_files, lambda);
+ return false;
}
const FileSpecList &CompileUnit::GetSupportFiles() {
Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
===================================================================
--- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
+++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
@@ -53,9 +53,9 @@
bool ParseDebugMacros(lldb_private::CompileUnit &comp_unit) override;
- void
- ForEachExternalModule(lldb_private::CompileUnit &comp_unit,
- llvm::function_ref<void(lldb::ModuleSP)> f) override;
+ bool ForEachExternalModule(
+ lldb_private::CompileUnit &, llvm::DenseSet<lldb_private::SymbolFile *> &,
+ llvm::function_ref<bool(lldb_private::Module &)>) override;
bool ParseSupportFiles(lldb_private::CompileUnit &comp_unit,
lldb_private::FileSpecList &support_files) override;
@@ -114,6 +114,11 @@
uint32_t max_matches,
llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
lldb_private::TypeMap &types) override;
+ void
+ FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> context,
+ lldb_private::LanguageSet languages,
+ llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+ lldb_private::TypeMap &types) override;
lldb_private::CompilerDeclContext FindNamespace(
lldb_private::ConstString name,
const lldb_private::CompilerDeclContext *parent_decl_ctx) override;
Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp
===================================================================
--- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp
+++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp
@@ -652,12 +652,15 @@
return false;
}
-void SymbolFileDWARFDebugMap::ForEachExternalModule(
- CompileUnit &comp_unit, llvm::function_ref<void(ModuleSP)> f) {
+bool SymbolFileDWARFDebugMap::ForEachExternalModule(
+ CompileUnit &comp_unit,
+ llvm::DenseSet<lldb_private::SymbolFile *> &visited_symbol_files,
+ llvm::function_ref<bool(Module &)> f) {
std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
SymbolFileDWARF *oso_dwarf = GetSymbolFile(comp_unit);
if (oso_dwarf)
- oso_dwarf->ForEachExternalModule(comp_unit, f);
+ return oso_dwarf->ForEachExternalModule(comp_unit, visited_symbol_files, f);
+ return false;
}
bool SymbolFileDWARFDebugMap::ParseSupportFiles(CompileUnit &comp_unit,
@@ -1183,6 +1186,16 @@
});
}
+void SymbolFileDWARFDebugMap::FindTypes(
+ llvm::ArrayRef<CompilerContext> context, LanguageSet languages,
+ llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+ TypeMap &types) {
+ ForEachSymbolFile([&](SymbolFileDWARF *oso_dwarf) -> bool {
+ oso_dwarf->FindTypes(context, languages, searched_symbol_files, types);
+ return false;
+ });
+}
+
//
// uint32_t
// SymbolFileDWARFDebugMap::FindTypes (const SymbolContext& sc, const
Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
===================================================================
--- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
+++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
@@ -105,9 +105,9 @@
bool ParseDebugMacros(lldb_private::CompileUnit &comp_unit) override;
- void
- ForEachExternalModule(lldb_private::CompileUnit &comp_unit,
- llvm::function_ref<void(lldb::ModuleSP)> f) override;
+ bool ForEachExternalModule(
+ lldb_private::CompileUnit &, llvm::DenseSet<lldb_private::SymbolFile *> &,
+ llvm::function_ref<bool(lldb_private::Module &)>) override;
bool ParseSupportFiles(lldb_private::CompileUnit &comp_unit,
lldb_private::FileSpecList &support_files) override;
Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp
===================================================================
--- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp
+++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp
@@ -850,16 +850,32 @@
return functions_added;
}
-void SymbolFileDWARF::ForEachExternalModule(
- CompileUnit &comp_unit, llvm::function_ref<void(ModuleSP)> f) {
- UpdateExternalModuleListIfNeeded();
+bool SymbolFileDWARF::ForEachExternalModule(
+ CompileUnit &comp_unit,
+ llvm::DenseSet<lldb_private::SymbolFile *> &visited_symbol_files,
+ llvm::function_ref<bool(Module &)> lambda) {
+ // Only visit each symbol file once.
+ if (!visited_symbol_files.insert(this).second)
+ return false;
+ UpdateExternalModuleListIfNeeded();
for (auto &p : m_external_type_modules) {
ModuleSP module = p.second;
- f(module);
- for (std::size_t i = 0; i < module->GetNumCompileUnits(); ++i)
- module->GetCompileUnitAtIndex(i)->ForEachExternalModule(f);
+ if (!module)
+ continue;
+
+ // Invoke the action and potentially early-exit.
+ if (lambda(*module))
+ return true;
+
+ for (std::size_t i = 0; i < module->GetNumCompileUnits(); ++i) {
+ auto cu = module->GetCompileUnitAtIndex(i);
+ bool early_exit = cu->ForEachExternalModule(visited_symbol_files, lambda);
+ if (early_exit)
+ return true;
+ }
}
+ return false;
}
bool SymbolFileDWARF::ParseSupportFiles(CompileUnit &comp_unit,
@@ -2492,8 +2508,19 @@
if (Type *matching_type = ResolveType(die, true, true))
// We found a type pointer, now find the shared pointer form our type
// list.
+
types.InsertUnique(matching_type->shared_from_this());
}
+
+ // Next search through the reachable Clang modules. This only applies for
+ // DWARF objects compiled with -gmodules that haven't been processed by
+ // dsymutil.
+ UpdateExternalModuleListIfNeeded();
+
+ for (const auto &pair : m_external_type_modules)
+ if (ModuleSP external_module_sp = pair.second)
+ external_module_sp->FindTypes(pattern, languages, searched_symbol_files,
+ types);
}
CompilerDeclContext
Index: lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.h
===================================================================
--- lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.h
+++ lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.h
@@ -128,7 +128,8 @@
const DWARFDIE &parent_die);
/// Parse a structure, class, or union type DIE.
- lldb::TypeSP ParseStructureLikeDIE(const DWARFDIE &die,
+ lldb::TypeSP ParseStructureLikeDIE(const lldb_private::SymbolContext &sc,
+ const DWARFDIE &die,
ParsedDWARFTypeAttributes &attrs);
lldb_private::Type *GetTypeForDIE(const DWARFDIE &die);
@@ -160,7 +161,8 @@
const DWARFDIE &die, lldb::TypeSP type_sp);
/// Follow Clang Module Skeleton CU references to find a type definition.
- lldb::TypeSP ParseTypeFromClangModule(const DWARFDIE &die,
+ lldb::TypeSP ParseTypeFromClangModule(const lldb_private::SymbolContext &sc,
+ const DWARFDIE &die,
lldb_private::Log *log);
// Return true if this type is a declaration to a type in an external
Index: lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp
===================================================================
--- lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp
+++ lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp
@@ -168,7 +168,8 @@
return lldb::ModuleSP();
}
-TypeSP DWARFASTParserClang::ParseTypeFromClangModule(const DWARFDIE &die,
+TypeSP DWARFASTParserClang::ParseTypeFromClangModule(const SymbolContext &sc,
+ const DWARFDIE &die,
Log *log) {
ModuleSP dwo_module_sp = GetContainingClangModule(die);
if (!dwo_module_sp)
@@ -189,19 +190,23 @@
searched_symbol_files, pcm_types);
if (pcm_types.Empty()) {
// Since this type is defined in one of the Clang modules imported
- // by this symbol file, search all of them.
+ // by this symbol file, search all of them. Instead of calling
+ // sym_file->FindTypes(), which would return this again, go straight
+ // to the imported modules.
auto &sym_file = die.GetCU()->GetSymbolFileDWARF();
- for (const auto &name_module : sym_file.getExternalTypeModules()) {
- if (!name_module.second)
- continue;
- name_module.second->GetSymbolFile()->FindTypes(
- decl_context, languages, searched_symbol_files, pcm_types);
- if (pcm_types.GetSize())
- break;
- }
+
+ // Well-formed clang modules never form cycles; guard against corrupted
+ // ones by inserting the current file.
+ searched_symbol_files.insert(&sym_file);
+ sym_file.ForEachExternalModule(
+ *sc.comp_unit, searched_symbol_files, [&](Module &module) {
+ module.GetSymbolFile()->FindTypes(decl_context, languages,
+ searched_symbol_files, pcm_types);
+ return pcm_types.GetSize();
+ });
}
- if (pcm_types.GetSize() != 1)
+ if (!pcm_types.GetSize())
return TypeSP();
// We found a real definition for this type in the Clang module, so lets use
@@ -491,7 +496,7 @@
// contain those
if (encoding_die &&
encoding_die.GetAttributeValueAsUnsigned(DW_AT_declaration, 0) == 1) {
- type_sp = ParseTypeFromClangModule(die, log);
+ type_sp = ParseTypeFromClangModule(sc, die, log);
if (type_sp)
return type_sp;
}
@@ -667,13 +672,13 @@
case DW_TAG_class_type: {
assert((!type_sp && !clang_type) &&
"Did not expect partially computed structure-like type");
- TypeSP struct_like_type_sp = ParseStructureLikeDIE(die, attrs);
+ TypeSP struct_like_type_sp = ParseStructureLikeDIE(sc, die, attrs);
return UpdateSymbolContextScopeForType(sc, die, struct_like_type_sp);
}
case DW_TAG_enumeration_type: {
if (attrs.is_forward_declaration) {
- type_sp = ParseTypeFromClangModule(die, log);
+ type_sp = ParseTypeFromClangModule(sc, die, log);
if (type_sp)
return type_sp;
@@ -1339,7 +1344,8 @@
}
TypeSP
-DWARFASTParserClang::ParseStructureLikeDIE(const DWARFDIE &die,
+DWARFASTParserClang::ParseStructureLikeDIE(const SymbolContext &sc,
+ const DWARFDIE &die,
ParsedDWARFTypeAttributes &attrs) {
TypeSP type_sp;
CompilerType clang_type;
@@ -1473,7 +1479,7 @@
// See if the type comes from a Clang module and if so, track down
// that type.
- type_sp = ParseTypeFromClangModule(die, log);
+ type_sp = ParseTypeFromClangModule(sc, die, log);
if (type_sp)
return type_sp;
Index: lldb/source/Plugins/ExpressionParser/Clang/ClangUserExpression.cpp
===================================================================
--- lldb/source/Plugins/ExpressionParser/Clang/ClangUserExpression.cpp
+++ lldb/source/Plugins/ExpressionParser/Clang/ClangUserExpression.cpp
@@ -42,6 +42,7 @@
#include "lldb/Symbol/CompileUnit.h"
#include "lldb/Symbol/Function.h"
#include "lldb/Symbol/ObjectFile.h"
+#include "lldb/Symbol/SymbolFile.h"
#include "lldb/Symbol/SymbolVendor.h"
#include "lldb/Symbol/Type.h"
#include "lldb/Symbol/VariableList.h"
@@ -478,15 +479,18 @@
files.AppendIfUnique(f);
// We also need to look at external modules in the case of -gmodules as they
// contain the support files for libc++ and the C library.
- sc.comp_unit->ForEachExternalModule([&files](lldb::ModuleSP module) {
- for (std::size_t i = 0; i < module->GetNumCompileUnits(); ++i) {
- const FileSpecList &support_files =
- module->GetCompileUnitAtIndex(i)->GetSupportFiles();
- for (const FileSpec &f : support_files) {
- files.AppendIfUnique(f);
- }
- }
- });
+ llvm::DenseSet<SymbolFile *> visited_symbol_files;
+ sc.comp_unit->ForEachExternalModule(
+ visited_symbol_files, [&files](Module &module) {
+ for (std::size_t i = 0; i < module.GetNumCompileUnits(); ++i) {
+ const FileSpecList &support_files =
+ module.GetCompileUnitAtIndex(i)->GetSupportFiles();
+ for (const FileSpec &f : support_files) {
+ files.AppendIfUnique(f);
+ }
+ }
+ return false;
+ });
LLDB_LOG(log, "[C++ module config] Found {0} support files to analyze",
files.GetSize());
Index: lldb/include/lldb/Symbol/SymbolFile.h
===================================================================
--- lldb/include/lldb/Symbol/SymbolFile.h
+++ lldb/include/lldb/Symbol/SymbolFile.h
@@ -122,9 +122,28 @@
virtual size_t ParseFunctions(CompileUnit &comp_unit) = 0;
virtual bool ParseLineTable(CompileUnit &comp_unit) = 0;
virtual bool ParseDebugMacros(CompileUnit &comp_unit) = 0;
- virtual void
- ForEachExternalModule(CompileUnit &comp_unit,
- llvm::function_ref<void(lldb::ModuleSP)> f) {}
+
+ /// Apply a lambda to each external lldb::Module referenced by this
+ /// compilation unit. Recursively also descends into the referenced external
+ /// modules of any encountered compilation unit.
+ ///
+ /// \param[in] lambda
+ /// The lambda that should be applied to every function. The lambda can
+ /// return true if the iteration should be aborted earlier.
+ ///
+ /// \param visited_symbol_files
+ /// A set of SymbolFiles that were already visited to avoid
+ /// visiting one file more than once.
+ ///
+ /// \return
+ /// If the lambda early-exited, this function returns true to
+ /// propagate the early exit.
+ virtual bool ForEachExternalModule(
+ lldb_private::CompileUnit &comp_unit,
+ llvm::DenseSet<lldb_private::SymbolFile *> &visited_symbol_files,
+ llvm::function_ref<bool(Module &)> lambda) {
+ return false;
+ }
virtual bool ParseSupportFiles(CompileUnit &comp_unit,
FileSpecList &support_files) = 0;
virtual size_t ParseTypes(CompileUnit &comp_unit) = 0;
Index: lldb/include/lldb/Symbol/CompileUnit.h
===================================================================
--- lldb/include/lldb/Symbol/CompileUnit.h
+++ lldb/include/lldb/Symbol/CompileUnit.h
@@ -19,6 +19,7 @@
#include "lldb/lldb-enumerations.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
namespace lldb_private {
/// \class CompileUnit CompileUnit.h "lldb/Symbol/CompileUnit.h"
@@ -241,9 +242,20 @@
/// compilation unit. Recursively also descends into the referenced external
/// modules of any encountered compilation unit.
///
- /// \param[in] f
- /// The lambda that should be applied to every module.
- void ForEachExternalModule(llvm::function_ref<void(lldb::ModuleSP)> f);
+ /// \param visited_symbol_files
+ /// A set of SymbolFiles that were already visited to avoid
+ /// visiting one file more than once.
+ ///
+ /// \param[in] lambda
+ /// The lambda that should be applied to every function. The lambda can
+ /// return true if the iteration should be aborted earlier.
+ ///
+ /// \return
+ /// If the lambda early-exited, this function returns true to
+ /// propagate the early exit.
+ virtual bool ForEachExternalModule(
+ llvm::DenseSet<lldb_private::SymbolFile *> &visited_symbol_files,
+ llvm::function_ref<bool(Module &)> lambda);
/// Get the compile unit's support file list.
///
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
