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

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.

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
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 function UIDs to indexes in m_functions.
+  llvm::DenseMap<lldb::user_id_t, size_t> m_function_uid_to_index;
   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.

source/Symbol/CompileUnit.cpp

if (!m_functions.empty()) {
     s->EOL();
   }
 }
 
 //----------------------------------------------------------------------
 // Add a function to this compile unit
 //----------------------------------------------------------------------
 void CompileUnit::AddFunction(FunctionSP &funcSP) {
+  m_function_uid_to_index[funcSP->GetID()] = m_functions.size();
   // 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;
 }

 //              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_function_uid_to_index.find(func_uid);
+  if (it == m_function_uid_to_index.end())
+    return FunctionSP();
+  return m_functions[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) {