ObjectFileMachO: Replace std::map with llvm::DenseMap (NFC)

[aprantl]

Summary

This makes parsing the symbol table of clang ~10ms faster. (Hashtable versus tree).

[labath]

lldb/include/lldb/Utility/ConstString.h

441

You could declare the specific instantiation (DenseMapInfo<ConstString>) as a friend instead of the whole template.

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

2496

It looks like the values for these are coming straight from the object file (aka user input). Are you ok with asserting on "resolvers" like 0xff...ff ?

[aprantl]

Pavel correctly pointed out that this isn't necessarily correct, because the addresses could conflict with the Tombstone/Empty keys.

lldb/include/lldb/Utility/ConstString.h

 //===-- ConstString.h -------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef liblldb_ConstString_h_
 #define liblldb_ConstString_h_
 
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/Support/FormatVariadic.h"
 
 #include <stddef.h>
 
 namespace lldb_private {
 class Stream;
 }
 namespace llvm {
public:
   /// any other values as a byte size for the entire string pool.
   ///
   /// \return
   ///     The number of bytes that the global string pool occupies
   ///     in memory.
   static size_t StaticMemorySize();
 
 protected:
+  template <typename T> friend struct ::llvm::DenseMapInfo;
+  /// Only used by DenseMapInfo.
+  static ConstString FromStringPoolPointer(const char *ptr) {
+    ConstString s;
+    s.m_string = ptr;
+    return s;
+  };
+
   // Member variables
   const char *m_string;
 };
 
 /// Stream the string value \a str to the stream \a s
 Stream &operator<<(Stream &s, ConstString str);
 
 } // namespace lldb_private
 
 namespace llvm {
 template <> struct format_provider<lldb_private::ConstString> {
   static void format(const lldb_private::ConstString &CS, llvm::raw_ostream &OS,
                      llvm::StringRef Options);
 };
+
+/// DenseMapInfo implementation.
+/// \{
+template <> struct DenseMapInfo<lldb_private::ConstString> {
+  static inline lldb_private::ConstString getEmptyKey() {
+    return lldb_private::ConstString::FromStringPoolPointer(
+        DenseMapInfo<const char *>::getEmptyKey());
+  }
+  static inline lldb_private::ConstString getTombstoneKey() {
+    return lldb_private::ConstString::FromStringPoolPointer(
+        DenseMapInfo<const char *>::getTombstoneKey());
+  }
+  static unsigned getHashValue(lldb_private::ConstString val) {
+    return DenseMapInfo<const char *>::getHashValue(val.m_string);
+  }
+  static bool isEqual(lldb_private::ConstString LHS,
+                      lldb_private::ConstString RHS) {
+    return LHS == RHS;
+  }
+};
+/// \}
 }
 
 #endif // liblldb_ConstString_h_

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

struct TrieEntryWithOffset {
   bool operator<(const TrieEntryWithOffset &other) const {
     return (nodeOffset < other.nodeOffset);
   }
 };
 
 static bool ParseTrieEntries(DataExtractor &data, lldb::offset_t offset,
                              const bool is_arm,
                              std::vector<llvm::StringRef> &nameSlices,
-                             std::set<lldb::addr_t> &resolver_addresses,
+                             llvm::DenseSet<lldb::addr_t> &resolver_addresses,
                              std::vector<TrieEntryWithOffset> &output) {
   if (!data.ValidOffset(offset))
     return true;
 
   const uint64_t terminalSize = data.GetULEB128(&offset);
   lldb::offset_t children_offset = offset + terminalSize;
   if (terminalSize != 0) {
     TrieEntryWithOffset e(offset);
#endif
 
   MachSymtabSectionInfo section_info(section_list);
   std::vector<uint32_t> N_FUN_indexes;
   std::vector<uint32_t> N_NSYM_indexes;
   std::vector<uint32_t> N_INCL_indexes;
   std::vector<uint32_t> N_BRAC_indexes;
   std::vector<uint32_t> N_COMM_indexes;
   typedef std::multimap<uint64_t, uint32_t> ValueToSymbolIndexMap;
-  typedef std::map<uint32_t, uint32_t> NListIndexToSymbolIndexMap;
-  typedef std::map<const char *, uint32_t> ConstNameToSymbolIndexMap;
+  typedef llvm::DenseMap<uint32_t, uint32_t> NListIndexToSymbolIndexMap;
+  typedef llvm::DenseMap<const char *, uint32_t> ConstNameToSymbolIndexMap;
   ValueToSymbolIndexMap N_FUN_addr_to_sym_idx;
   ValueToSymbolIndexMap N_STSYM_addr_to_sym_idx;
   ConstNameToSymbolIndexMap N_GSYM_name_to_sym_idx;
   // Any symbols that get merged into another will get an entry in this map
   // so we know
   NListIndexToSymbolIndexMap m_nlist_idx_to_sym_idx;
   uint32_t nlist_idx = 0;
   Symbol *symbol_ptr = nullptr;
 
   uint32_t sym_idx = 0;
   Symbol *sym = nullptr;
   size_t num_syms = 0;
   std::string memory_symbol_name;
   uint32_t unmapped_local_symbols_found = 0;
 
   std::vector<TrieEntryWithOffset> trie_entries;
-  std::set<lldb::addr_t> resolver_addresses;
+  llvm::DenseSet<lldb::addr_t> resolver_addresses;
 
   if (dyld_trie_data.GetByteSize() > 0) {
     std::vector<llvm::StringRef> nameSlices;
     ParseTrieEntries(dyld_trie_data, 0, is_arm, nameSlices, resolver_addresses,
                      trie_entries);
 
     ConstString text_segment_name("__TEXT");
     SectionSP text_segment_sp =
if (dsc_data_sp) {
               MapFileData(dsc_filespec, localSymbolsSize, localSymbolsOffset);
 
           if (dsc_local_symbols_data_sp) {
             DataExtractor dsc_local_symbols_data(dsc_local_symbols_data_sp,
                                                  byte_order, addr_byte_size);
 
             offset = 0;
 
-            typedef std::map<ConstString, uint16_t> UndefinedNameToDescMap;
-            typedef std::map<uint32_t, ConstString> SymbolIndexToName;
+            typedef llvm::DenseMap<ConstString, uint16_t> UndefinedNameToDescMap;
+            typedef llvm::DenseMap<uint32_t, ConstString> SymbolIndexToName;
             UndefinedNameToDescMap undefined_name_to_desc;
             SymbolIndexToName reexport_shlib_needs_fixup;
 
             // Read the local_symbols_infos struct in one shot
             struct lldb_copy_dyld_cache_local_symbols_info local_symbols_info;
             dsc_local_symbols_data.GetU32(&offset,
                                           &local_symbols_info.nlistOffset, 6);
 
if (dsc_data_sp) {
 
                       if (is_debug == false) {
                         if (type == eSymbolTypeCode) {
                           // See if we can find a N_FUN entry for any code
                           // symbols. If we do find a match, and the name
                           // matches, then we can merge the two into just the
                           // function symbol to avoid duplicate entries in
                           // the symbol table
-                          std::pair<ValueToSymbolIndexMap::const_iterator,
-                                    ValueToSymbolIndexMap::const_iterator>
-                              range;
-                          range =
+                          auto range =
                               N_FUN_addr_to_sym_idx.equal_range(nlist.n_value);
                           if (range.first != range.second) {
                             bool found_it = false;
-                            for (ValueToSymbolIndexMap::const_iterator pos =
-                                     range.first;
+                            for (const auto pos = range.first;
                                  pos != range.second; ++pos) {
                               if (sym[sym_idx].GetMangled().GetName(
                                       lldb::eLanguageTypeUnknown,
                                       Mangled::ePreferMangled) ==
                                   sym[pos->second].GetMangled().GetName(
                                       lldb::eLanguageTypeUnknown,
                                       Mangled::ePreferMangled)) {
                                 m_nlist_idx_to_sym_idx[nlist_idx] = pos->second;
if (dsc_data_sp) {
                                    type == eSymbolTypeObjCClass ||
                                    type == eSymbolTypeObjCMetaClass ||
                                    type == eSymbolTypeObjCIVar) {
                           // See if we can find a N_STSYM entry for any data
                           // symbols. If we do find a match, and the name
                           // matches, then we can merge the two into just the
                           // Static symbol to avoid duplicate entries in the
                           // symbol table
-                          std::pair<ValueToSymbolIndexMap::const_iterator,
-                                    ValueToSymbolIndexMap::const_iterator>
-                              range;
-                          range = N_STSYM_addr_to_sym_idx.equal_range(
+                          auto range = N_STSYM_addr_to_sym_idx.equal_range(
                               nlist.n_value);
                           if (range.first != range.second) {
                             bool found_it = false;
-                            for (ValueToSymbolIndexMap::const_iterator pos =
-                                     range.first;
+                            for (const auto pos = range.first;
                                  pos != range.second; ++pos) {
                               if (sym[sym_idx].GetMangled().GetName(
                                       lldb::eLanguageTypeUnknown,
                                       Mangled::ePreferMangled) ==
                                   sym[pos->second].GetMangled().GetName(
                                       lldb::eLanguageTypeUnknown,
                                       Mangled::ePreferMangled)) {
                                 m_nlist_idx_to_sym_idx[nlist_idx] = pos->second;
if (nlist_data.GetByteSize() > 0) {
     if (unmapped_local_symbols_found) {
       assert(m_dysymtab.ilocalsym == 0);
       nlist_data_offset += (m_dysymtab.nlocalsym * nlist_byte_size);
       nlist_idx = m_dysymtab.nlocalsym;
     } else {
       nlist_idx = 0;
     }
 
-    typedef std::map<ConstString, uint16_t> UndefinedNameToDescMap;
-    typedef std::map<uint32_t, ConstString> SymbolIndexToName;
+    typedef llvm::DenseMap<ConstString, uint16_t> UndefinedNameToDescMap;
+    typedef llvm::DenseMap<uint32_t, ConstString> SymbolIndexToName;
     UndefinedNameToDescMap undefined_name_to_desc;
     SymbolIndexToName reexport_shlib_needs_fixup;
     for (; nlist_idx < symtab_load_command.nsyms; ++nlist_idx) {
       struct nlist_64 nlist;
       if (!ParseNList(nlist_data, nlist_data_offset, nlist_byte_size, nlist))
         break;
 
       const char *symbol_name_non_abi_mangled = nullptr;