[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 (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/test/ELF/strtab-dedup.s

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