Performance: Add a set of visited SymbolFiles to other the FindFiles variant.

[aprantl]

Summary

This is basically the same bug as in r260434 again. SymbolFileDWARF::FindTypes has exponential worst-case when digging through dependency DAG of .pcms because each object file and pcm may depend on an already-visited .pcm, which may again have dependencies. Fixed here by carrying a set of already visited SymbolFiles around.

rdar://problem/56993424

lldb/include/lldb/Core/Module.h

FindTypes(ConstString type_name, bool exact_match, size_t max_matches,
             llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
             TypeList &types);
 
   /// Find types by name.
   ///
   /// 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,
                              ConstString type_name, bool exact_match);
 
   /// Find types by name that are in a namespace. This function is used by the
   /// expression parser when searches need to happen in an exact namespace
   /// scope.

lldb/include/lldb/Symbol/SymbolFile.h

virtual void FindFunctions(const RegularExpression &regex,
                              bool include_inlines, SymbolContextList &sc_list);
   virtual void
   FindTypes(ConstString name, const CompilerDeclContext *parent_decl_ctx,
             uint32_t max_matches,
             llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
             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,
                              std::vector<ConstString> &mangled_names);
 
   virtual void GetTypes(lldb_private::SymbolContextScope *sc_scope,
                         lldb::TypeClass type_mask,
                         lldb_private::TypeList &type_list) = 0;

lldb/source/Core/Module.cpp

void Module::FindTypes(
   }
   if (typesmap.GetSize()) {
     SymbolContext sc;
     sc.module_sp = shared_from_this();
     sc.SortTypeList(typesmap, types);
   }
 }
 
-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) {
   if (!m_did_load_symfile.load()) {
     std::lock_guard<std::recursive_mutex> guard(m_mutex);
     if (!m_did_load_symfile.load() && can_create) {
       ObjectFile *obj_file = GetObjectFile();
       if (obj_file != nullptr) {

lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h

void FindFunctions(const RegularExpression &regex, bool include_inlines,
                      SymbolContextList &sc_list) override;
 
   void FindTypes(ConstString name, const CompilerDeclContext *parent_decl_ctx,
                  uint32_t max_matches,
                  llvm::DenseSet<SymbolFile *> &searched_symbol_files,
                  TypeMap &types) override;
 
   void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
+                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
                  TypeMap &types) override;
 
   llvm::Expected<TypeSystem &>
   GetTypeSystemForLanguage(lldb::LanguageType language) override {
     return llvm::make_error<llvm::StringError>(
         "SymbolFileBreakpad does not support GetTypeSystemForLanguage",
         llvm::inconvertibleErrorCode());
   }

lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

void SymbolFileBreakpad::FindFunctions(const RegularExpression &regex,
   // TODO
 }
 
 void SymbolFileBreakpad::FindTypes(
     ConstString name, const CompilerDeclContext *parent_decl_ctx,
     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);
   Module &module = *m_objfile_sp->GetModule();
   addr_t base = GetBaseFileAddress();
   if (base == LLDB_INVALID_ADDRESS) {
     LLDB_LOG(log, "Unable to fetch the base address of object file. Skipping "
                   "symtab population.");

lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

TypeSP DWARFASTParserClang::ParseTypeFromDWO(const DWARFDIE &die, Log *log) {
   // units as breadcrumbs to find them.
   llvm::SmallVector<CompilerContext, 4> decl_context;
   die.GetDeclContext(decl_context);
   TypeMap dwo_types;
 
   // 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();
 
     // Since this type is defined in one of the Clang modules imported
     // by this symbol file, search all of them.
     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, dwo_types);
+      name_module.second->GetSymbolFile()->FindTypes(
+          decl_context, languages, searched_symbol_files, dwo_types);
       if (dwo_types.GetSize())
         break;
     }
   }
 
   if (dwo_types.GetSize() != 1)
     return TypeSP();
 

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

public:
   FindTypes(lldb_private::ConstString name,
             const lldb_private::CompilerDeclContext *parent_decl_ctx,
             uint32_t max_matches,
             llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
             lldb_private::TypeMap &types) override;
 
   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,
                 lldb::TypeClass type_mask,
                 lldb_private::TypeList &type_list) override;
 
   llvm::Expected<lldb_private::TypeSystem &>
   GetTypeSystemForLanguage(lldb::LanguageType language) override;

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

 }
 
 void SymbolFileDWARF::FindTypes(
     ConstString name, const CompilerDeclContext *parent_decl_ctx,
     uint32_t max_matches,
     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;
 
   Log *log(LogChannelDWARF::GetLogIfAll(DWARF_LOG_LOOKUPS));
 
   if (log) {
     if (parent_decl_ctx)
if (parent_decl_ctx) {
           log,
           "SymbolFileDWARF::FindTypes (sc, name=\"%s\", parent_decl_ctx "
           "= NULL, max_matches=%u, type_list) => %u",
           name.GetCString(), max_matches, types.GetSize());
     }
   }
 }
 
-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;
 
   ConstString name = pattern.back().name;
 
   if (!name)
     return;

lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.h

void FindFunctions(const RegularExpression &regex, bool include_inlines,
                      SymbolContextList &sc_list) override;
 
   void FindTypes(ConstString name, const CompilerDeclContext *parent_decl_ctx,
                  uint32_t max_matches,
                  llvm::DenseSet<SymbolFile *> &searched_symbol_files,
                  TypeMap &types) override;
 
   void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
+                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
                  TypeMap &types) override;
 
   llvm::Expected<TypeSystem &>
   GetTypeSystemForLanguage(lldb::LanguageType language) override;
 
   CompilerDeclContext
   FindNamespace(ConstString name,
                 const CompilerDeclContext *parent_decl_ctx) override;

lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp

void SymbolFileNativePDB::FindTypes(
 
   searched_symbol_files.clear();
   searched_symbol_files.insert(this);
 
   // There is an assumption 'name' is not a regex
   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,
                                           TypeMap &types) {
 
   std::vector<TypeIndex> matches = m_index->tpi().findRecordsByName(name);
   if (max_matches > 0 && max_matches < matches.size())
     matches.resize(max_matches);

lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.h

public:
   FindTypes(lldb_private::ConstString name,
             const lldb_private::CompilerDeclContext *parent_decl_ctx,
             uint32_t max_matches,
             llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
             lldb_private::TypeMap &types) override;
 
   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 &regex,
                         uint32_t max_matches, lldb_private::TypeMap &types);
 
   void GetTypes(lldb_private::SymbolContextScope *sc_scope,
                 lldb::TypeClass type_mask,
                 lldb_private::TypeList &type_list) override;

lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp

while (auto result = results->getNext()) {
     auto iter = m_types.find(result->getSymIndexId());
     if (iter == m_types.end())
       continue;
     types.Insert(iter->second);
     ++matches;
   }
 }
 
-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,
 
 void SymbolFilePDB::GetTypesForPDBSymbol(const llvm::pdb::PDBSymbol &pdb_symbol,
                                          uint32_t type_mask,
                                          TypeCollection &type_collection) {
   bool can_parse = false;
   switch (pdb_symbol.getSymTag()) {
   case PDB_SymType::ArrayType:
     can_parse = ((type_mask & eTypeClassArray) != 0);

lldb/source/Symbol/SymbolFile.cpp

 
 void SymbolFile::FindTypes(
     ConstString name, const CompilerDeclContext *parent_decl_ctx,
     uint32_t max_matches,
     llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
     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
   // enabled in debug builds or when the correct macro is set.
 #if defined(LLDB_CONFIGURATION_DEBUG)
   // We assert that we have to module lock by trying to acquire the lock from a
   // different thread. Note that we must abort if the result is true to
   // guarantee correctness.

lldb/tools/lldb-test/lldb-test.cpp

if (!Language.empty())
     languages.Insert(Language::GetLanguageTypeFromString(Language));
   
   DenseSet<SymbolFile *> SearchedFiles;
   TypeMap Map;
   if (!Name.empty())
     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;
   Map.Dump(&Stream, false);
   outs() << Stream.GetData() << "\n";
   return Error::success();
 }