[ELF] Deduplicate names of local symbols only with -O2

[MaskRay]

Summary

The deduplication requires a DenseMap of the same size of the local part of
.strtab . I optimized it in e20544543478b259eb09fa0a253d4fb1a5525d9e but it is
still quite slow.

For Release build of clang, deduplication makes .strtab 1.1% smaller and makes the link 3% slower.
For chrome, deduplication makes .strtab 0.1% smaller and makes the link 6% slower.

I suggest that we only perform the optimization with -O2 (default is -O1).
Not deduplicating local symbol names will simplify parallel symbol table write.

[peter.smith]

I'm OK with the change. It looks like a good trade off for non-release links. I think it will be worth an entry in the release notes. Something like: "LLD no longer deduplicates local symbol names at the default optimization level of -O1. This results in a larger output ELF file but a faster link time. Use optimization level -O2 to restore the deduplication."

[MaskRay]

Thanks for the note. Added to ReleaseNotes.rst

[peter.smith]

LGTM thanks for the release note.

[MaskRay]

This .strtab deduplication makes parallel .symtab write difficult. I suspect we may need to disable it entirely in the future.

[bd1976llvm]

In D118577#3288196, @MaskRay wrote:

This .strtab deduplication makes parallel .symtab write difficult. I suspect we may need to disable it entirely in the future.

Thanks for making this optimization. I suspect disabling entirely is acceptable because the deduplication could be done via post-processing. There's going to be a trade off between the features offered and the amount of parallelism - I think that's fine as long as the speed up is reasonable. Users are evidently willing to go to great lengths to restructure their builds to get the most out of the build tools (game code often uses unity builds, for example).

lld/ELF/SyntheticSections.cpp

for (const Symbol *b : entries) {
     buf += target->gotEntrySize;
   }
 }
 
 StringTableSection::StringTableSection(StringRef name, bool dynamic)
     : SyntheticSection(dynamic ? (uint64_t)SHF_ALLOC : 0, SHT_STRTAB, 1, name),
       dynamic(dynamic) {
   // ELF string tables start with a NUL byte.
-  addString("");
+  strings.push_back("");
+  size = 1;
 }
 
 // Adds a string to the string table. If `hashIt` is true we hash and check for
 // duplicates. It is optional because the name of global symbols are already
 // uniqued and hashing them again has a big cost for a small value: uniquing
 // them with some other string that happens to be the same.
 unsigned StringTableSection::addString(StringRef s, bool hashIt) {
   if (hashIt) {
     auto r = stringMap.try_emplace(CachedHashStringRef(s), size);
     if (!r.second)
       return r.first->second;
   }
+  if (s.empty())
+    return 0;
   unsigned ret = this->size;
   this->size = this->size + s.size() + 1;
   strings.push_back(s);
   return ret;
 }
 
 void StringTableSection::writeTo(uint8_t *buf) {
   for (StringRef s : strings) {
for (auto &p : arr)
     for (SymbolTableEntry &entry : p.second)
       *i++ = entry;
 }
 
 void SymbolTableBaseSection::addSymbol(Symbol *b) {
   // Adding a local symbol to a .dynsym is a bug.
   assert(this->type != SHT_DYNSYM || !b->isLocal());
 
-  bool hashIt = b->isLocal();
+  bool hashIt = b->isLocal() && config->optimize >= 2;
   symbols.push_back({b, strTabSec.addString(b->getName(), hashIt)});
 }
 
 size_t SymbolTableBaseSection::getSymbolIndex(Symbol *sym) {
   if (this == mainPart->dynSymTab.get())
     return sym->dynsymIndex;
 
   // Initializes symbol lookup tables lazily. This is used only for -r,

lld/docs/ReleaseNotes.rst

* ``--export-dynamic-symbol-list`` has been added.
   (`D107317 <https://reviews.llvm.org/D107317>`_)
 * ``--why-extract`` has been added to query why archive members/lazy object files are extracted.
   (`D109572 <https://reviews.llvm.org/D109572>`_)
 * ``e_entry`` no longer falls back to the address of ``.text`` if the entry symbol does not exist.
   Instead, a value of 0 will be written.
   (`D110014 <https://reviews.llvm.org/D110014>`_)
 * If ``-Map`` is specified, ``--cref`` will be printed to the specified file.
   (`D114663 <https://reviews.llvm.org/D114663>`_)
+* No longer deduplicate local symbol names at the default optimization level of ``-O1``.
+  This results in a larger ``.strtab`` (usually less than 1%) but a faster link
+  time. Use optimization level ``-O2`` to restore the deduplication.
 
 Architecture specific changes:
 
 * The x86-32 port now supports TLSDESC (``-mtls-dialect=gnu2``).
   (`D112582 <https://reviews.llvm.org/D112582>`_)
 * The x86-64 port now handles non-RAX/non-adjacent ``R_X86_64_GOTPC32_TLSDESC``
   and ``R_X86_64_TLSDESC_CALL`` (``-mtls-dialect=gnu2``).
   (`D114416 <https://reviews.llvm.org/D114416>`_)

lld/test/ELF/strtab-dedup.s

+# REQUIRES: x86
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/a.s -o %t/a.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/b.s -o %t/b.o
+
+## By default local symbol names are not deduplicated.
+# RUN: ld.lld %t/a.o %t/b.o -o %t/a
+# RUN: llvm-readelf -p .strtab %t/a | FileCheck %s --check-prefix=NODEDUP
+
+# NODEDUP:        [     1]  local
+# NODEDUP-NEXT:   [     7]  local
+# NODEDUP-NEXT:   [     d]  foo
+# NODEDUP-EMPTY:
+
+## -O2 deduplicates local symbol names.
+# RUN: ld.lld -O2 %t/a.o %t/b.o -o %t/a
+# RUN: llvm-readelf -p .strtab %t/a | FileCheck %s --check-prefix=DEDUP
+
+# DEDUP:        [     1]  local
+# DEDUP-NEXT:   [     7]  foo
+# DEDUP-EMPTY:
+
+#--- a.s
+.global foo
+foo:
+local:
+  ret
+
+#--- b.s
+.weak foo
+foo:
+local:
+  ret