Re-enable std::function formatter with fixes to improve non-cached lookup performance

[shafik]

Summary

This PR depends on D67111

Performance issues lead to the libc++ std::function formatter to be disabled. We addressed some of those performance issues by adding caching see D67111

This PR fixes the first lookup performance by not using FindSymbolsMatchingRegExAndType(...) and instead finding the compilation unit the std::function wrapped callable should be in and then searching for the callable directly in the CU.

[friss]

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.cpp

274

Why a new variable?

287

Doesn't matter too much for lambdas, but shouldn't this be "operator()" ?
Is this guaranteed to return a valid index? Should we assert on it?

293

this is basically is_lambda. As we filter it above, why do we need this test?

source/Symbol/CompileUnit.cpp

101

This seems pretty expensive. Can we Force the parsing of the functions just in the compiler unit rather than the whole symbol file? If you are using a dSYM, then this is going to load all the debug information in one go.

[friss]

source/Symbol/CompileUnit.cpp

101

Sorry, I somehow missed that this takes a CU as argument. This seems fine.

[aprantl]

include/lldb/Symbol/CompileUnit.h

172

Document what does the bool return value do?

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.cpp

299

func_sp?

[aprantl]

Seems fine otherwise, I think.

include/lldb/Symbol/CompileUnit.h

174

perhaps calling it is_match makes this more obvious?

[shafik]

After updating branch the stepping test started failing. It was failing because the __invoke case was subtly broken in this patch. Fixing that case opened up a lot of refactoring opportunities. So this patch ends up being a large refactor and in many ways a simplification now.

[shafik]

@aprantl you will want to take a second look at this, I did some major refactoring.

[jingham]

Why not have the FindFunctions lambda take a FunctionSP? It would be easy to get the Function name out of the function in the lambda, and that would make the function more general (and also match what the Foreach does...

[aprantl]

lldb/include/lldb/Symbol/CompileUnit.h

169 ↗

(On Diff #228533)

This doesn't explain what the bool return does.

[shafik]

In D69913#1739579, @jingham wrote:

Why not have the FindFunctions lambda take a FunctionSP? It would be easy to get the Function name out of the function in the lambda, and that would make the function more general (and also match what the Foreach does...

It was not obvious how they were using it at first, good catch.

[shafik]

• Adjust comment
• matching_lambda argument is now FunctionSP to match ForeachFunction signature.

[shafik]

Applying clang-format

include/lldb/Symbol/CompileUnit.h

public:
   /// \note Prefer using FindFunctionByUID over this if possible.
   ///
   /// \param[in] lambda
   ///     The lambda that should be applied to every function. The lambda can
   ///     return true if the iteration should be aborted earlier.
   void ForeachFunction(
       llvm::function_ref<bool(const lldb::FunctionSP &)> lambda) const;
 
+  /// Find a function in the compile unit based on the predicate matching_lambda
+  ///
+  /// \param[in] matching_lambda
+  ///     A predicate used to evaluate each function name.
+  ///
+  /// \return
+  ///   The FunctionSP containing the first matching entry.
+  lldb::FunctionSP
+  FindFunction(llvm::function_ref<bool(const llvm::StringRef)> matching_lambda);
+
   /// Dump the compile unit contents to the stream \a s.
   ///
   /// \param[in] s
   ///     The stream to which to dump the object description.
   ///
   /// \param[in] show_context
   ///     If \b true, variables will dump their symbol context
   ///     information.

packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-stl/libcxx/function/TestLibCxxFunction.py

class LibCxxFunctionTestCase(TestBase):
 
     # Run frame var for a variable twice. Verify we do not hit the cache
     # the first time but do the second time.
     def run_frame_var_check_cache_use(self, variable, result_to_match):
         self.runCmd("log timers reset")
         self.expect("frame variable " + variable,
                     substrs=[variable + " =  " + result_to_match])
         self.expect("log timers dump",
-                   substrs=["lldb_private::Module::FindSymbolsMatchingRegExAndType"])
+                   substrs=["lldb_private::CompileUnit::FindFunction"])
 
         self.runCmd("log timers reset")
         self.expect("frame variable " + variable,
                     substrs=[variable + " =  " + result_to_match])
         self.expect("log timers dump",
                    matching=False,
-                   substrs=["lldb_private::Module::FindSymbolsMatchingRegExAndType"])
+                   substrs=["lldb_private::CompileUnit::FindFunction"])
 
 
-    # Temporarily skipping for everywhere b/c we are disabling the std::function formatter
-    # due to performance issues but plan on turning it back on once they are addressed.
-    @skipIf
     @add_test_categories(["libc++"])
     def test(self):
         """Test that std::function as defined by libc++ is correctly printed by LLDB"""
         self.build()
         self.runCmd("file " + self.getBuildArtifact("a.out"), CURRENT_EXECUTABLE_SET)
 
         bkpt = self.target().FindBreakpointByID(
             lldbutil.run_break_set_by_source_regexp(
def test(self):
         lldbutil.continue_to_breakpoint(self.process(), bkpt)
 
         self.run_frame_var_check_cache_use("add_num2_f", "Lambda in File main.cpp at Line 21")
 
         lldbutil.continue_to_breakpoint(self.process(), bkpt)
 
         self.run_frame_var_check_cache_use("f2", "Lambda in File main.cpp at Line 43")
         self.run_frame_var_check_cache_use("f3", "Lambda in File main.cpp at Line 47")
-        self.run_frame_var_check_cache_use("f4", "Function in File main.cpp at Line 16")
+        # TODO reenable this case when std::function formatter supports
+        # general callable object case.
+        #self.run_frame_var_check_cache_use("f4", "Function in File main.cpp at Line 16")
 
         # These cases won't hit the cache at all but also don't require
         # an expensive lookup.
         self.expect("frame variable f1",
                     substrs=['f1 =  Function = foo(int, int)'])
 
         self.expect("frame variable f5",
                     substrs=['f5 =  Function = Bar::add_num(int) const'])

packages/Python/lldbsuite/test/lang/cpp/std-function-step-into-callable/TestStdFunctionStepIntoCallable.py

def test(self):
         self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetFileSpec().GetFilename(), self.main_source) ;
         process.Continue()
 
         thread.StepInto()
         self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetLine(), self.source_lambda_f3_line ) ;
         self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetFileSpec().GetFilename(), self.main_source) ;
         process.Continue()
 
-        thread.StepInto()
-        self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetLine(), self.source_bar_operator_line ) ;
-        self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetFileSpec().GetFilename(), self.main_source) ;
-        process.Continue()
+        # TODO reenable this case when std::function formatter supports
+        # general callable object case.
+        #thread.StepInto()
+        #self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetLine(), self.source_bar_operator_line ) ;
+        #self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetFileSpec().GetFilename(), self.main_source) ;
+        #process.Continue()
 
         thread.StepInto()
         self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetLine(), self.source_bar_add_num_line ) ;
         self.assertEqual( thread.GetFrameAtIndex(0).GetLineEntry().GetFileSpec().GetFilename(), self.main_source) ;
         process.Continue()

packages/Python/lldbsuite/test/lang/cpp/std-function-step-into-callable/main.cpp

int main (int argc, char *argv[])
   Bar bar1 ;
   std::function<int ()> f4( bar1 ) ;
   std::function<int (const Bar&, int)> f5 = &Bar::add_num;
   std::function<int(Bar const&)> f_mem = &Bar::num_;
 
   return f_mem(bar1) +     // Set break point at this line.
          f1(acc,acc) +     // Source main invoking f1
          f2(acc) +         // Set break point at this line.
-         f3(acc+1,acc+2) + // Set break point at this line. 
-         f4() +            // Set break point at this line. 
+         f3(acc+1,acc+2) + // Set break point at this line.
+         // TODO reenable this case when std::function formatter supports
+         // general callable object case.
+         //f4() +            // Set break point at this line.
          f5(bar1, 10);     // Set break point at this line.
 }

source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.cpp

AddCXXSynthetic(
       ConstString("^(std::__[[:alnum:]]+::)shared_ptr<.+>(( )?&)?$"),
       stl_synth_flags, true);
   AddCXXSynthetic(
       cpp_category_sp,
       lldb_private::formatters::LibcxxSharedPtrSyntheticFrontEndCreator,
       "weak_ptr synthetic children",
       ConstString("^(std::__[[:alnum:]]+::)weak_ptr<.+>(( )?&)?$"),
       stl_synth_flags, true);
+  AddCXXSummary(cpp_category_sp,
+                lldb_private::formatters::LibcxxFunctionSummaryProvider,
+                "libc++ std::function summary provider",
+                ConstString("^std::__[[:alnum:]]+::function<.+>$"),
+                stl_summary_flags, true);
 
   stl_summary_flags.SetDontShowChildren(false);
   stl_summary_flags.SetSkipPointers(false);
   AddCXXSummary(cpp_category_sp,
                 lldb_private::formatters::LibcxxContainerSummaryProvider,
                 "libc++ std::bitset summary provider",
                 ConstString("^std::__[[:alnum:]]+::bitset<.+>(( )?&)?$"),
                 stl_summary_flags, true);

source/Plugins/LanguageRuntime/CPlusPlus/CPPLanguageRuntime.cpp

 
 #include "lldb/Symbol/Block.h"
 #include "lldb/Symbol/Variable.h"
 #include "lldb/Symbol/VariableList.h"
 
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Core/UniqueCStringMap.h"
 #include "lldb/Symbol/ClangASTContext.h"
+#include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Target/ABI.h"
 #include "lldb/Target/ExecutionContext.h"
 #include "lldb/Target/RegisterContext.h"
 #include "lldb/Target/SectionLoadList.h"
 #include "lldb/Target/StackFrame.h"
 #include "lldb/Target/ThreadPlanRunToAddress.h"
 #include "lldb/Target/ThreadPlanStepInRange.h"
+#include "lldb/Utility/Timer.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 static ConstString g_this = ConstString("this");
 
 char CPPLanguageRuntime::ID = 0;
 
bool CPPLanguageRuntime::GetObjectDescription(
     Stream &str, Value &value, ExecutionContextScope *exe_scope) {
   // C++ has no generic way to do this.
   return false;
 }
 
 CPPLanguageRuntime::LibCppStdFunctionCallableInfo
 CPPLanguageRuntime::FindLibCppStdFunctionCallableInfo(
     lldb::ValueObjectSP &valobj_sp) {
+  static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
+  Timer scoped_timer(func_cat,
+                     "CPPLanguageRuntime::FindLibCppStdFunctionCallableInfo");
+
   LibCppStdFunctionCallableInfo optional_info;
 
   if (!valobj_sp)
     return optional_info;
 
   // Member __f_ has type __base*, the contents of which will hold:
   // 1) a vtable entry which may hold type information needed to discover the
   //    lambda being called
CPPLanguageRuntime::FindLibCppStdFunctionCallableInfo(
   // 1) a lambda we know at compile time. We will obtain the name of the lambda
   //    from the first template pameter from __func's vtable. We will look up
   //    the lambda's operator()() and obtain the line table entry.
   // 2) a lambda we know at runtime. A pointer to the lambdas __invoke method
   //    will be stored after the vtable. We will obtain the lambdas name from
   //    this entry and lookup operator()() and obtain the line table entry.
   // 3) a callable object via operator()(). We will obtain the name of the
   //    object from the first template parameter from __func's vtable. We will
-  //    look up the objectc operator()() and obtain the line table entry.
+  //    look up the objects operator()() and obtain the line table entry.
   // 4) a member function. A pointer to the function will stored after the
   //    we will obtain the name from this pointer.
   // 5) a free function. A pointer to the function will stored after the vtable
   //    we will obtain the name from this pointer.
   ValueObjectSP member__f_(
       valobj_sp->GetChildMemberWithName(ConstString("__f_"), true));
 
   if (member__f_) {
CPPLanguageRuntime::FindLibCppStdFunctionCallableInfo(
   // First item pointed to by __f_ should be the pointer to the vtable for
   // a __base object.
   lldb::addr_t vtable_address =
       process->ReadPointerFromMemory(member__f_pointer_value, status);
 
   if (status.Fail())
     return optional_info;
 
+  lldb::addr_t vtable_address_first_entry =
+      process->ReadPointerFromMemory(vtable_address + address_size, status);
+
+  if (status.Fail())
+    return optional_info;
+
   lldb::addr_t address_after_vtable = member__f_pointer_value + address_size;
   // As commened above we may not have a function pointer but if we do we will
   // need it.
   lldb::addr_t possible_function_address =
       process->ReadPointerFromMemory(address_after_vtable, status);
 
   if (status.Fail())
     return optional_info;
 
   Target &target = process->GetTarget();
 
   if (target.GetSectionLoadList().IsEmpty())
     return optional_info;
 
+  Address vtable_first_entry_resolved;
+
+  if (!target.GetSectionLoadList().ResolveLoadAddress(
+          vtable_address_first_entry, vtable_first_entry_resolved))
+    return optional_info;
+
   Address vtable_addr_resolved;
   SymbolContext sc;
-  Symbol *symbol;
+  Symbol *symbol = nullptr;
 
   if (!target.GetSectionLoadList().ResolveLoadAddress(vtable_address,
                                                       vtable_addr_resolved))
     return optional_info;
 
   target.GetImages().ResolveSymbolContextForAddress(
       vtable_addr_resolved, eSymbolContextEverything, sc);
   symbol = sc.symbol;
CPPLanguageRuntime::FindLibCppStdFunctionCallableInfo(
   // vtable. We will use a process of elimination to drop through each case
   // and obtain the data we need.
   if (target.GetSectionLoadList().ResolveLoadAddress(
           possible_function_address, function_address_resolved)) {
     target.GetImages().ResolveSymbolContextForAddress(
         function_address_resolved, eSymbolContextEverything, sc);
     symbol = sc.symbol;
   }
-    
-    auto contains_lambda_identifier = []( llvm::StringRef & str_ref ) {
-        return str_ref.contains("$_") || str_ref.contains("'lambda'");
-    };
+  auto contains_lambda_identifier = [](llvm::StringRef &str_ref) {
 
   // Case 4 or 5
   // We eliminate these cases early because they don't need the potentially
   // expensive lookup through the symbol table.
   if (symbol && !symbol->GetName().GetStringRef().startswith("vtable for") &&
       !contains_lambda_identifier(first_template_parameter) &&
       !symbol->GetName().GetStringRef().contains("__invoke")) {
     optional_info.callable_case =
         LibCppStdFunctionCallableCase::FreeOrMemberFunction;
     optional_info.callable_address = function_address_resolved;
     optional_info.callable_symbol = *symbol;
 
     return optional_info;
   }
 
   auto get_name = [&first_template_parameter, &symbol, contains_lambda_identifier]() {
     // Given case 1:
     //
     //    main::$_0
     //    Bar::add_num2(int)::'lambda'(int)
     //
     // we want to append ::operator()()
     if (contains_lambda_identifier(first_template_parameter))
-      return llvm::Regex::escape(first_template_parameter.str()) +
-             R"(::operator\(\)\(.*\))";
+      return first_template_parameter.str() + R"(::operator()()";
 
     if (symbol != nullptr &&
         symbol->GetName().GetStringRef().contains("__invoke")) {
 
       llvm::StringRef symbol_name = symbol->GetName().GetStringRef();
       size_t pos2 = symbol_name.find_last_of(':');
 
       // Given case 2:
       //
       //    main::$_1::__invoke(...)
       //
       // We want to slice off __invoke(...) and append operator()()
       std::string lambda_operator =
-          llvm::Regex::escape(symbol_name.slice(0, pos2 + 1).str()) +
-          R"(operator\(\)\(.*\))";
+          symbol_name.slice(0, pos2 + 1).str() + R"(operator()()";
 
       return lambda_operator;
     }
 
     // Case 3
-    return first_template_parameter.str() + R"(::operator\(\)\(.*\))";
+    return first_template_parameter.str() + R"(::operator()()";
     ;
   };
 
   std::string func_to_match = get_name();
 
   auto it = CallableLookupCache.find(func_to_match);
   if (it != CallableLookupCache.end())
     return it->second;
 
   SymbolContextList scl;
 
-  target.GetImages().FindSymbolsMatchingRegExAndType(
-      RegularExpression{R"(^)" + func_to_match}, eSymbolTypeAny, scl, true);
+  CompileUnit *vtable_cu =
+      vtable_first_entry_resolved.CalculateSymbolContextCompileUnit();
+  llvm::StringRef name_to_use = func_to_match;
+  bool is_lambda = contains_lambda_identifier(name_to_use);
+
+  // Case 3, we have a callable object instead of a lambda
+  //
+  // TODO
+  // We currently don't support this case a callable object may have multiple
+  // operator()() varying on const/non-const and number of arguments and we
+  // don't have a way to currently distinguish them so we will bail out now.
+  if (!is_lambda)
+    return {};
+
+  size_t pos = llvm::StringRef::npos;
+  pos = name_to_use.find("::operator");
+
+  if (vtable_cu) {
+    llvm::StringRef sliced_name = name_to_use.slice(0, pos);
+    auto find_function_matcher = [sliced_name](llvm::StringRef name) {
+      if (name.startswith(sliced_name) && name.contains("operator"))
+        if (name.contains("$_") || name.contains("'lambda'"))
+          return true;
+
+      return false;
+    };
+
+    lldb::FunctionSP fsp = vtable_cu->FindFunction(find_function_matcher);
+
+    if (fsp) {
+      SymbolContext sc;
+      fsp->CalculateSymbolContext(&sc);
+      scl.Append(sc);
+    }
+  }
 
   // Case 1,2 or 3
   if (scl.GetSize() >= 1) {
     SymbolContext sc2 = scl[0];
 
     AddressRange range;
     sc2.GetAddressRange(eSymbolContextEverything, 0, false, range);
 

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

lldb::LanguageType SymbolFileDWARF::ParseLanguage(CompileUnit &comp_unit) {
   DWARFUnit *dwarf_cu = GetDWARFCompileUnit(&comp_unit);
   if (dwarf_cu)
     return dwarf_cu->GetLanguageType();
   else
     return eLanguageTypeUnknown;
 }
 
 size_t SymbolFileDWARF::ParseFunctions(CompileUnit &comp_unit) {
+  static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
+  Timer scoped_timer(func_cat, "SymbolFileDWARF::ParseFunctions");
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
   DWARFUnit *dwarf_cu = GetDWARFCompileUnit(&comp_unit);
   if (!dwarf_cu)
     return 0;
 
   size_t functions_added = 0;
   std::vector<DWARFDIE> function_dies;
   dwarf_cu->AppendDIEsWithTag(DW_TAG_subprogram, function_dies);

source/Symbol/CompileUnit.cpp

 //===-- CompileUnit.cpp -----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Core/Module.h"
 #include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/SymbolFile.h"
 #include "lldb/Symbol/VariableList.h"
 #include "lldb/Target/Language.h"
+#include "lldb/Utility/Timer.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 CompileUnit::CompileUnit(const lldb::ModuleSP &module_sp, void *user_data,
                          const char *pathname, const lldb::user_id_t cu_sym_id,
                          lldb::LanguageType language,
                          lldb_private::LazyBool is_optimized)
llvm::sort(sorted_functions.begin(), sorted_functions.end(),
                return a->GetID() < b->GetID();
              });
 
   for (auto &f : sorted_functions)
     if (lambda(f))
       return;
 }
 
+lldb::FunctionSP CompileUnit::FindFunction(
+    llvm::function_ref<bool(const llvm::StringRef)> matching_lambda) {
+  static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
+  Timer scoped_timer(func_cat, "CompileUnit::FindFunction");
+
+  lldb::ModuleSP module = CalculateSymbolContextModule();
+
+  if (!module)
+    return {};
+
+  SymbolFile *symbol_file = module->GetSymbolFile();
+
+  if (!symbol_file)
+    return {};
+
+  // m_functions_by_uid is filled in lazily but we need all the entries.
+  symbol_file->ParseFunctions(*this);
+
+  for (auto &p : m_functions_by_uid) {
+    if (matching_lambda(p.second->GetName().GetStringRef()))
+      return p.second;
+  }
+  return {};
+}
+
 // Dump the current contents of this object. No functions that cause on demand
 // parsing of functions, globals, statics are called, so this is a good
 // function to call to get an idea of the current contents of the CompileUnit
 // object.
 void CompileUnit::Dump(Stream *s, bool show_context) const {
   const char *language = Language::GetNameForLanguageType(m_language);
 
   s->Printf("%p: ", static_cast<const void *>(this));