Expression eval lookup - prune methods without parsing

[jarin]

Summary

In large codebases, we sometimes see Module::FindFunctions (when called from
ClangExpressionDeclMap::FindExternalVisibleDecls) returning huge amounts of
functions. For example, a simple unreal engine example contains

10000 of functions with the name 'operator*'. Evaluating an expression "*x",

where x is an instance of a class, will cause all those function's decl
contexts to be parsed, taking multiple seconds. However, most of those
parsed contexts will be immediately thrown away because most of the
functions are methods.

With this patch, I am trying to avoid the parsing by checking method-ness
directly from debug info rather than from parsed contexts. This helps a lot:
our unreal engine expression evaluation pause goes roughly from 4.5s to 0.3s.

However, my patch feels wrong - ideally, we would ignore methods already
during lookup (in ManualDWARFIndex::GetFunctions).

A resonable solution would be to change the meaning of
eFunctionNameTypeFull to only mean mangled names, and if the caller
wanted methods and basenames, they would have to call with
eFunctionNameTypeFull | eFunctionNameTypeMethod |
eFunctionNameTypeBase. This would require some amount churn at
(Get|Find)Functions call sites. Also, I am not sure about implications
for Apple's lookup index.

Thoughts?

[labath]

A resonable solution would be to change the meaning of
eFunctionNameTypeFull to only mean mangled names, and if the caller
wanted methods and basenames, they would have to call with
eFunctionNameTypeFull | eFunctionNameTypeMethod |
eFunctionNameTypeBase. This would require some amount churn at
(Get|Find)Functions call sites. Also, I am not sure about implications
for Apple's lookup index.

This sounds like a good path forward to me. I remember being bothered by the fact that we were returning ns::foo, when someone asked for a function with a "full" name foo when I worked on this code last time. However, I didn't do anything about that back when I was working on this code, as it wasn't that relevant for me then...

Unfortunately, just simply removing the

m_set.function_basenames.Find(name, offsets);
m_set.function_methods.Find(name, offsets);

lines from the manual dwarf index causes a number of tests to fail, so it looks like there are thing which do depend on us returning the extra things here. These need to be tracked down and fixed (possibly by adding | eFunctionNameTypeMethod | eFunctionNameTypeBase to the FindFunctions call, possibly in another way...). As for the Apple (and debug_names) indexes, they can not avoid looking at the dwarf DIE to eliminate methods (because the accelerator tables don't store this information), but they can definitely check whether something is a method *after* looking at the DWARF but *before* returning from the GetFunctions method (which should still be a major improvement over status quo).

[aprantl]

I thought about something similar in the context of https://reviews.llvm.org/D68678 (that's for FIndTypes, but it we the same kind of problems there). Like Pavel said, it would be valuable to be able to filter after the accelerator table lookup, but before building, e.g., clang AST nodes.

[jarin]

Thanks for the feedback! We will experiment with filtering in GetFunctions sometime next week.

Regarding the FindTypes patch, it would be really nice to have that for Linux, as well. I see the type pruning (TypeMap::RemoveMismatchedTypes) taking several seconds for some expression evaluations; it is likely to be the same problem you are solving.

lldb/include/lldb/Symbol/Function.h

public:
   const Mangled &GetMangled() const { return m_mangled; }
 
   /// Get the DeclContext for this function, if available.
   ///
   /// \return
   ///     The DeclContext, or NULL if none exists.
   CompilerDeclContext GetDeclContext();
 
+  /// A quick test for being a method. This is used to filter out methods from
+  /// lists of functions without fully parsing debug info.
+  bool CanBeMethod();
+
   /// Get accessor for the type that describes the function return value type,
   /// and parameter types.
   ///
   /// \return
   ///     A type object pointer.
   Type *GetType();
 
   /// Get const accessor for the type that describes the function return value

lldb/include/lldb/Symbol/SymbolFile.h

virtual CompilerDecl GetDeclForUID(lldb::user_id_t uid) {
     return CompilerDecl();
   }
   virtual CompilerDeclContext GetDeclContextForUID(lldb::user_id_t uid) {
     return CompilerDeclContext();
   }
   virtual CompilerDeclContext GetDeclContextContainingUID(lldb::user_id_t uid) {
     return CompilerDeclContext();
   }
+  virtual bool CanBeMethod(lldb::user_id_t uid) { return true; }
   virtual uint32_t ResolveSymbolContext(const Address &so_addr,
                                         lldb::SymbolContextItem resolve_scope,
                                         SymbolContext &sc) = 0;
   virtual uint32_t ResolveSymbolContext(const FileSpec &file_spec,
                                         uint32_t line, bool check_inlines,
                                         lldb::SymbolContextItem resolve_scope,
                                         SymbolContextList &sc_list);
 

lldb/source/Plugins/ExpressionParser/Clang/ClangExpressionDeclMap.cpp

if (sc_list.GetSize() > 1) {
           Function *function = sym_ctx.function;
           if (!function) {
             sc_sym_list.Append(sym_ctx);
             continue;
           }
           // Filter out functions without declaration contexts, as well as
           // class/instance methods, since they'll be skipped in the code that
           // follows anyway.
+          if (function->CanBeMethod())
+            continue;
           CompilerDeclContext func_decl_context = function->GetDeclContext();
           if (!func_decl_context ||
               func_decl_context.IsClassMethod(nullptr, nullptr, nullptr))
             continue;
           // We can only prune functions for which we can copy the type.
           CompilerType func_clang_type =
               function->GetType()->GetFullCompilerType();
           CompilerType copied_func_type = GuardedCopyType(func_clang_type);

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

public:
   lldb_private::CompilerDecl GetDeclForUID(lldb::user_id_t uid) override;
 
   lldb_private::CompilerDeclContext
   GetDeclContextForUID(lldb::user_id_t uid) override;
 
   lldb_private::CompilerDeclContext
   GetDeclContextContainingUID(lldb::user_id_t uid) override;
 
+  bool CanBeMethod(lldb::user_id_t uid) override;
+
   void
   ParseDeclsForContext(lldb_private::CompilerDeclContext decl_ctx) override;
 
   uint32_t ResolveSymbolContext(const lldb_private::Address &so_addr,
                                 lldb::SymbolContextItem resolve_scope,
                                 lldb_private::SymbolContext &sc) override;
 
   uint32_t

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

SymbolFileDWARF::GetDeclContextContainingUID(lldb::user_id_t type_uid) {
   // Anytime we have a lldb::user_id_t, we must get the DIE by calling
   // SymbolFileDWARF::GetDIE(). See comments inside the
   // SymbolFileDWARF::GetDIE() for details.
   if (DWARFDIE die = GetDIE(type_uid))
     return die.GetContainingDeclContext();
   return CompilerDeclContext();
 }
 
+bool SymbolFileDWARF::CanBeMethod(lldb::user_id_t uid) {
+  std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
+  // Anytime we have a lldb::user_id_t, we must get the DIE by calling
+  // SymbolFileDWARF::GetDIE(). See comments inside the
+  // SymbolFileDWARF::GetDIE() for details.
+  if (DWARFDIE die = GetDIE(uid))
+    return die.IsMethod();
+  return true;
+}
+
 Type *SymbolFileDWARF::ResolveTypeUID(lldb::user_id_t type_uid) {
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
   // Anytime we have a lldb::user_id_t, we must get the DIE by calling
   // SymbolFileDWARF::GetDIE(). See comments inside the
   // SymbolFileDWARF::GetDIE() for details.
   if (DWARFDIE type_die = GetDIE(type_uid))
     return type_die.ResolveType();
   else

lldb/source/Symbol/Function.cpp

CompilerDeclContext Function::GetDeclContext() {
 
   if (module_sp) {
     if (SymbolFile *sym_file = module_sp->GetSymbolFile())
       return sym_file->GetDeclContextForUID(GetID());
   }
   return CompilerDeclContext();
 }
 
+bool Function::CanBeMethod() {
+  ModuleSP module_sp = CalculateSymbolContextModule();
+
+  if (module_sp) {
+    if (SymbolFile *sym_file = module_sp->GetSymbolFile())
+      return sym_file->CanBeMethod(GetID());
+  }
+  return true;
+}
+
 Type *Function::GetType() {
   if (m_type == nullptr) {
     SymbolContext sc;
 
     CalculateSymbolContext(&sc);
 
     if (!sc.module_sp)
       return nullptr;