Use a DenseMap for looking up functions by UID in CompileUnit::FindFunctionByUID

[teemperor]

Summary

Instead of iterating over our vector of functions, we might as well use a map here to
directly get the function we need.

Thanks to Vedant for pointing this out.

[vsk]

Thanks for doing this :)!

source/Symbol/CompileUnit.cpp

111 ↗

(On Diff #158876)

Is m_functions used to do anything crucial?

I see a use in Dump, but it seems like you could replace that use by copying the function map into a vector and sorting it. I see another use in GetFunctionAtIndex, but that API can be deleted entirely because its only user is lldb-test (via Module::ParseAllDebugSymbols). You'd just need to sink this block of code into CompileUnit:

for (size_t func_idx = 0;
     (sc.function = sc.comp_unit->GetFunctionAtIndex(func_idx).get()) !=
     nullptr;
     ++func_idx) {
  symbols->ParseFunctionBlocks(sc);

  // Parse the variables for this function and all its blocks
  symbols->ParseVariablesForContext(sc);
}

[teemperor]

• Replaced m_functions and instead copy the map to a temporary sorted vector and iterate over that.

[vsk]

Thanks, LGTM!

[teemperor]

• Passing shared_ptr to lambda now as const-ref.

lldb/trunk/include/lldb/Symbol/CompileUnit.h

 #include "lldb/Core/FileSpecList.h"
 #include "lldb/Core/ModuleChild.h"
 #include "lldb/Symbol/DebugMacros.h"
 #include "lldb/Symbol/Function.h"
 #include "lldb/Utility/Stream.h"
 #include "lldb/Utility/UserID.h"
 #include "lldb/lldb-enumerations.h"
 
+#include "llvm/ADT/DenseMap.h"
+
 namespace lldb_private {
 //----------------------------------------------------------------------
 /// @class CompileUnit CompileUnit.h "lldb/Symbol/CompileUnit.h"
 /// A class that describes a compilation unit.
 ///
 /// A representation of a compilation unit, or compiled source file.
 /// The UserID of the compile unit is specified by the SymbolFile plug-in and
 /// can have any value as long as the value is unique within the Module that
public:
   void SetLanguage(lldb::LanguageType language) {
     m_flags.Set(flagsParsedLanguage);
     m_language = language;
   }
 
   void GetDescription(Stream *s, lldb::DescriptionLevel level) const;
 
   //------------------------------------------------------------------
-  /// Get a shared pointer to a function in this compile unit by index.
+  /// Apply a lambda to each function in this compile unit.
   ///
-  /// Typically called when iterating though all functions in a compile unit
-  /// after all functions have been parsed. This provides raw access to the
-  /// function shared pointer list and will not cause the SymbolFile plug-in
-  /// to parse any unparsed functions.
+  /// This provides raw access to the function shared pointer list and will not
+  /// cause the SymbolFile plug-in to parse any unparsed functions.
   ///
-  /// @param[in] idx
-  ///     An index into the function list.
+  /// @note Prefer using FindFunctionByUID over this if possible.
   ///
-  /// @return
-  ///     A shared pointer to a function that might contain a NULL
-  ///     Function class pointer.
+  /// @param[in] lambda
+  ///     The lambda that should be applied to every function. The lambda can
+  ///     return true if the iteration should be aborted earlier.
   //------------------------------------------------------------------
-  lldb::FunctionSP GetFunctionAtIndex(size_t idx);
+  void ForeachFunction(
+      llvm::function_ref<bool(const lldb::FunctionSP &)> lambda) const;
 
   //------------------------------------------------------------------
   /// 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
public:
   bool GetIsOptimized();
 
 protected:
   void *m_user_data; ///< User data for the SymbolFile parser to store
                      ///information into.
   lldb::LanguageType
       m_language; ///< The programming language enumeration value.
   Flags m_flags;  ///< Compile unit flags that help with partial parsing.
-  std::vector<lldb::FunctionSP> m_functions; ///< The sparsely populated list of
-                                             ///shared pointers to functions
-  ///< that gets populated as functions get partially parsed.
+
+  /// Maps UIDs to functions.
+  llvm::DenseMap<lldb::user_id_t, lldb::FunctionSP> m_functions_by_uid;
   std::vector<ConstString> m_imported_modules; ///< All modules, including the
                                                ///current module, imported by
                                                ///this
                                                ///< compile unit.
   FileSpecList m_support_files; ///< Files associated with this compile unit's
                                 ///line table and declarations.
   std::unique_ptr<LineTable>
       m_line_table_ap; ///< Line table that will get parsed on demand.

lldb/trunk/source/Core/Module.cpp

void Module::ParseAllDebugSymbols() {
   for (size_t cu_idx = 0; cu_idx < num_comp_units; cu_idx++) {
     sc.comp_unit = symbols->GetCompileUnitAtIndex(cu_idx).get();
     if (sc.comp_unit) {
       sc.function = nullptr;
       symbols->ParseVariablesForContext(sc);
 
       symbols->ParseCompileUnitFunctions(sc);
 
-      for (size_t func_idx = 0;
-           (sc.function = sc.comp_unit->GetFunctionAtIndex(func_idx).get()) !=
-           nullptr;
-           ++func_idx) {
+      sc.comp_unit->ForeachFunction([&sc, &symbols](const FunctionSP &f) {
+        sc.function = f.get();
         symbols->ParseFunctionBlocks(sc);
-
         // Parse the variables for this function and all its blocks
         symbols->ParseVariablesForContext(sc);
-      }
+        return false;
+      });
 
       // Parse all types for this compile unit
       sc.function = nullptr;
       symbols->ParseTypes(sc);
     }
   }
 }
 

lldb/trunk/source/Symbol/CompileUnit.cpp

 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)
     : ModuleChild(module_sp), FileSpec(pathname, false), UserID(cu_sym_id),
-      m_user_data(user_data), m_language(language), m_flags(0), m_functions(),
+      m_user_data(user_data), m_language(language), m_flags(0),
       m_support_files(), m_line_table_ap(), m_variables(),
       m_is_optimized(is_optimized) {
   if (language != eLanguageTypeUnknown)
     m_flags.Set(flagsParsedLanguage);
   assert(module_sp);
 }
 
 CompileUnit::CompileUnit(const lldb::ModuleSP &module_sp, void *user_data,
                          const FileSpec &fspec, const lldb::user_id_t cu_sym_id,
                          lldb::LanguageType language,
                          lldb_private::LazyBool is_optimized)
     : ModuleChild(module_sp), FileSpec(fspec), UserID(cu_sym_id),
-      m_user_data(user_data), m_language(language), m_flags(0), m_functions(),
+      m_user_data(user_data), m_language(language), m_flags(0),
       m_support_files(), m_line_table_ap(), m_variables(),
       m_is_optimized(is_optimized) {
   if (language != eLanguageTypeUnknown)
     m_flags.Set(flagsParsedLanguage);
   assert(module_sp);
 }
 
 CompileUnit::~CompileUnit() {}

 
 void CompileUnit::GetDescription(Stream *s,
                                  lldb::DescriptionLevel level) const {
   const char *language = Language::GetNameForLanguageType(m_language);
   *s << "id = " << (const UserID &)*this << ", file = \""
      << (const FileSpec &)*this << "\", language = \"" << language << '"';
 }
 
+void CompileUnit::ForeachFunction(
+    llvm::function_ref<bool(const FunctionSP &)> lambda) const {
+  std::vector<lldb::FunctionSP> sorted_functions;
+  sorted_functions.reserve(m_functions_by_uid.size());
+  for (auto &p : m_functions_by_uid)
+    sorted_functions.push_back(p.second);
+  std::sort(sorted_functions.begin(), sorted_functions.end(),
+            [](const lldb::FunctionSP &a, const lldb::FunctionSP &b) {
+              return a->GetID() < b->GetID();
+            });
+
+  for (auto &f : sorted_functions)
+    if (lambda(f))
+      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));
   s->Indent();
   *s << "CompileUnit" << static_cast<const UserID &>(*this) << ", language = \""
      << language << "\", file = '" << static_cast<const FileSpec &>(*this)
      << "'\n";
 
   //  m_types.Dump(s);
 
   if (m_variables.get()) {
     s->IndentMore();
     m_variables->Dump(s, show_context);
     s->IndentLess();
   }
 
-  if (!m_functions.empty()) {
+  if (!m_functions_by_uid.empty()) {
     s->IndentMore();
-    std::vector<FunctionSP>::const_iterator pos;
-    std::vector<FunctionSP>::const_iterator end = m_functions.end();
-    for (pos = m_functions.begin(); pos != end; ++pos) {
-      (*pos)->Dump(s, show_context);
-    }
+    ForeachFunction([&s, show_context](const FunctionSP &f) {
+      f->Dump(s, show_context);
+      return false;
+    });
 
     s->IndentLess();
     s->EOL();
   }
 }
 
 //----------------------------------------------------------------------
 // Add a function to this compile unit
 //----------------------------------------------------------------------
 void CompileUnit::AddFunction(FunctionSP &funcSP) {
-  // TODO: order these by address
-  m_functions.push_back(funcSP);
-}
-
-FunctionSP CompileUnit::GetFunctionAtIndex(size_t idx) {
-  FunctionSP funcSP;
-  if (idx < m_functions.size())
-    funcSP = m_functions[idx];
-  return funcSP;
+  m_functions_by_uid[funcSP->GetID()] = funcSP;
 }
 
 //----------------------------------------------------------------------
 // Find functions using the Mangled::Tokens token list. This function currently
 // implements an interactive approach designed to find all instances of certain
 // functions. It isn't designed to the quickest way to lookup functions as it
 // will need to iterate through all functions and see if they match, though it
 // does provide a powerful and context sensitive way to search for all

 //              if (func_tokens.MatchesQuery (tokens))
 //                  s << "demangled MATCH found: " << demangled << "\n";
 //          }
 //      }
 //  }
 //}
 
 FunctionSP CompileUnit::FindFunctionByUID(lldb::user_id_t func_uid) {
-  FunctionSP funcSP;
-  if (!m_functions.empty()) {
-    std::vector<FunctionSP>::const_iterator pos;
-    std::vector<FunctionSP>::const_iterator end = m_functions.end();
-    for (pos = m_functions.begin(); pos != end; ++pos) {
-      if ((*pos)->GetID() == func_uid) {
-        funcSP = *pos;
-        break;
-      }
-    }
-  }
-  return funcSP;
+  auto it = m_functions_by_uid.find(func_uid);
+  if (it == m_functions_by_uid.end())
+    return FunctionSP();
+  return it->second;
 }
 
 lldb::LanguageType CompileUnit::GetLanguage() {
   if (m_language == eLanguageTypeUnknown) {
     if (m_flags.IsClear(flagsParsedLanguage)) {
       m_flags.Set(flagsParsedLanguage);
       SymbolVendor *symbol_vendor = GetModule()->GetSymbolVendor();
       if (symbol_vendor) {