Author: Adrian Prantl Date: 2019-11-12T09:38:37-08:00 New Revision: 3b73dcdc9656e156c4380454150b8986c5b9aad1
URL: https://github.com/llvm/llvm-project/commit/3b73dcdc9656e156c4380454150b8986c5b9aad1 DIFF: https://github.com/llvm/llvm-project/commit/3b73dcdc9656e156c4380454150b8986c5b9aad1.diff LOG: Performance: Add a set of visited SymbolFiles to the other FindFiles variant. This is basically the same bug as in r260434. SymbolFileDWARF::FindTypes has exponential worst-case when digging through dependency DAG of .pcm files because each object file and .pcm file may depend on an already-visited .pcm file, which may again have dependencies. Fixed here by carrying a set of already visited SymbolFiles around. rdar://problem/56993424 Differential Revision: https://reviews.llvm.org/D70106 Added: Modified: lldb/include/lldb/Core/Module.h lldb/include/lldb/Symbol/SymbolFile.h lldb/source/Core/Module.cpp lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.h lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.h lldb/source/Symbol/SymbolFile.cpp lldb/tools/lldb-test/lldb-test.cpp Removed: ################################################################################ diff --git a/lldb/include/lldb/Core/Module.h b/lldb/include/lldb/Core/Module.h index 89b731427e3f..0f1d276337c1 100644 --- a/lldb/include/lldb/Core/Module.h +++ b/lldb/include/lldb/Core/Module.h @@ -429,7 +429,11 @@ class Module : public std::enable_shared_from_this<Module>, /// This behaves like the other FindTypes method but allows to /// specify a DeclContext and a language for the type being searched /// for. + /// + /// \param searched_symbol_files + /// Prevents one file from being visited multiple times. void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files, TypeMap &types); lldb::TypeSP FindFirstType(const SymbolContext &sc, diff --git a/lldb/include/lldb/Symbol/SymbolFile.h b/lldb/include/lldb/Symbol/SymbolFile.h index 6724b425abf3..3c52766f39d3 100644 --- a/lldb/include/lldb/Symbol/SymbolFile.h +++ b/lldb/include/lldb/Symbol/SymbolFile.h @@ -193,9 +193,14 @@ class SymbolFile : public PluginInterface { TypeMap &types); /// Find types specified by a CompilerContextPattern. - /// \param languages Only return results in these languages. - virtual void FindTypes(llvm::ArrayRef<CompilerContext> pattern, - LanguageSet languages, TypeMap &types); + /// \param languages + /// Only return results in these languages. + /// \param searched_symbol_files + /// Prevents one file from being visited multiple times. + virtual void + FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files, + TypeMap &types); virtual void GetMangledNamesForFunction(const std::string &scope_qualified_name, diff --git a/lldb/source/Core/Module.cpp b/lldb/source/Core/Module.cpp index aef3f3e3b4b0..a14bd3d370a1 100644 --- a/lldb/source/Core/Module.cpp +++ b/lldb/source/Core/Module.cpp @@ -1006,12 +1006,14 @@ void Module::FindTypes( } } -void Module::FindTypes(llvm::ArrayRef<CompilerContext> pattern, - LanguageSet languages, TypeMap &types) { +void Module::FindTypes( + llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files, + TypeMap &types) { static Timer::Category func_cat(LLVM_PRETTY_FUNCTION); Timer scoped_timer(func_cat, LLVM_PRETTY_FUNCTION); if (SymbolFile *symbols = GetSymbolFile()) - symbols->FindTypes(pattern, languages, types); + symbols->FindTypes(pattern, languages, searched_symbol_files, types); } SymbolFile *Module::GetSymbolFile(bool can_create, Stream *feedback_strm) { diff --git a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp index f84cf0c5368d..c77ddd378873 100644 --- a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp +++ b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp @@ -307,8 +307,9 @@ void SymbolFileBreakpad::FindTypes( uint32_t max_matches, llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) {} -void SymbolFileBreakpad::FindTypes(llvm::ArrayRef<CompilerContext> pattern, - LanguageSet languages, TypeMap &types) {} +void SymbolFileBreakpad::FindTypes( + llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) {} void SymbolFileBreakpad::AddSymbols(Symtab &symtab) { Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS); diff --git a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h index a10138cdf92f..1748c6484ab9 100644 --- a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h +++ b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h @@ -112,6 +112,7 @@ class SymbolFileBreakpad : public SymbolFile { TypeMap &types) override; void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) override; llvm::Expected<TypeSystem &> diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp index 42e25f727e4b..b129f999a288 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp @@ -150,7 +150,9 @@ TypeSP DWARFASTParserClang::ParseTypeFromDWO(const DWARFDIE &die, Log *log) { // The type in the Clang module must have the same language as the current CU. LanguageSet languages; languages.Insert(die.GetCU()->GetLanguageType()); - dwo_module_sp->GetSymbolFile()->FindTypes(decl_context, languages, dwo_types); + llvm::DenseSet<SymbolFile *> searched_symbol_files; + dwo_module_sp->GetSymbolFile()->FindTypes(decl_context, languages, + searched_symbol_files, dwo_types); if (dwo_types.Empty()) { if (!IsClangModuleFwdDecl(die)) return TypeSP(); @@ -161,8 +163,8 @@ TypeSP DWARFASTParserClang::ParseTypeFromDWO(const DWARFDIE &die, Log *log) { for (const auto &name_module : sym_file.getExternalTypeModules()) { if (!name_module.second) continue; - name_module.second->GetSymbolFile()->FindTypes(decl_context, - languages, dwo_types); + name_module.second->GetSymbolFile()->FindTypes( + decl_context, languages, searched_symbol_files, dwo_types); if (dwo_types.GetSize()) break; } diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp index f43537d20200..12ae16ee176d 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp +++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp @@ -2366,12 +2366,10 @@ void SymbolFileDWARF::FindTypes( llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files, TypeMap &types) { std::lock_guard<std::recursive_mutex> guard(GetModuleMutex()); - // Make sure we haven't already searched this SymbolFile before... - if (searched_symbol_files.count(this)) + // Make sure we haven't already searched this SymbolFile before. + if (!searched_symbol_files.insert(this).second) return; - searched_symbol_files.insert(this); - DWARFDebugInfo *info = DebugInfo(); if (!info) return; @@ -2453,8 +2451,13 @@ void SymbolFileDWARF::FindTypes( } } -void SymbolFileDWARF::FindTypes(llvm::ArrayRef<CompilerContext> pattern, - LanguageSet languages, TypeMap &types) { +void SymbolFileDWARF::FindTypes( + llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) { + // Make sure we haven't already searched this SymbolFile before. + if (!searched_symbol_files.insert(this).second) + return; + std::lock_guard<std::recursive_mutex> guard(GetModuleMutex()); if (pattern.empty()) return; diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h index 04cb11d426be..616c7f45bb5a 100644 --- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h +++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h @@ -190,6 +190,7 @@ class SymbolFileDWARF : public lldb_private::SymbolFile, void FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> pattern, lldb_private::LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, lldb_private::TypeMap &types) override; void GetTypes(lldb_private::SymbolContextScope *sc_scope, diff --git a/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp b/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp index 33b8da3b543b..5829a1c03435 100644 --- a/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp +++ b/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp @@ -1259,8 +1259,9 @@ void SymbolFileNativePDB::FindTypes( FindTypesByName(name.GetStringRef(), max_matches, types); } -void SymbolFileNativePDB::FindTypes(llvm::ArrayRef<CompilerContext> pattern, - LanguageSet languages, TypeMap &types) {} +void SymbolFileNativePDB::FindTypes( + llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) {} void SymbolFileNativePDB::FindTypesByName(llvm::StringRef name, uint32_t max_matches, diff --git a/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.h b/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.h index ca7de0e7d1ed..e89cb2c0a7c8 100644 --- a/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.h +++ b/lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.h @@ -131,6 +131,7 @@ class SymbolFileNativePDB : public SymbolFile { TypeMap &types) override; void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) override; llvm::Expected<TypeSystem &> diff --git a/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp b/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp index 854e735b5f83..b108cb405ed9 100644 --- a/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp +++ b/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp @@ -1562,9 +1562,10 @@ void SymbolFilePDB::FindTypesByName( } } -void SymbolFilePDB::FindTypes(llvm::ArrayRef<CompilerContext> pattern, - LanguageSet languages, - lldb_private::TypeMap &types) {} +void SymbolFilePDB::FindTypes( + llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, + lldb_private::TypeMap &types) {} void SymbolFilePDB::GetTypesForPDBSymbol(const llvm::pdb::PDBSymbol &pdb_symbol, uint32_t type_mask, diff --git a/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.h b/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.h index df717bbbbdb0..c041dab80cc7 100644 --- a/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.h +++ b/lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.h @@ -134,6 +134,7 @@ class SymbolFilePDB : public lldb_private::SymbolFile { void FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> pattern, lldb_private::LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, lldb_private::TypeMap &types) override; void FindTypesByRegex(const lldb_private::RegularExpression ®ex, diff --git a/lldb/source/Symbol/SymbolFile.cpp b/lldb/source/Symbol/SymbolFile.cpp index c4f3a9c1a8c8..f892d0908609 100644 --- a/lldb/source/Symbol/SymbolFile.cpp +++ b/lldb/source/Symbol/SymbolFile.cpp @@ -134,7 +134,9 @@ void SymbolFile::FindTypes( TypeMap &types) {} void SymbolFile::FindTypes(llvm::ArrayRef<CompilerContext> pattern, - LanguageSet languages, TypeMap &types) {} + LanguageSet languages, + llvm::DenseSet<SymbolFile *> &searched_symbol_files, + TypeMap &types) {} void SymbolFile::AssertModuleLock() { // The code below is too expensive to leave enabled in release builds. It's diff --git a/lldb/tools/lldb-test/lldb-test.cpp b/lldb/tools/lldb-test/lldb-test.cpp index 504bbbe6dabf..cf84da5e3a38 100644 --- a/lldb/tools/lldb-test/lldb-test.cpp +++ b/lldb/tools/lldb-test/lldb-test.cpp @@ -529,7 +529,7 @@ Error opts::symbols::findTypes(lldb_private::Module &Module) { Symfile.FindTypes(ConstString(Name), ContextPtr, UINT32_MAX, SearchedFiles, Map); else - Module.FindTypes(parseCompilerContext(), languages, Map); + Module.FindTypes(parseCompilerContext(), languages, SearchedFiles, Map); outs() << formatv("Found {0} types:\n", Map.GetSize()); StreamString Stream; _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits