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

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.

Reviewed By: peter.smith

Differential Revision: https://reviews.llvm.org/D118577

3 files changed, 41 insertions, 2 deletions

diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index 36a226c..986c130 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -1230,7 +1230,8 @@ 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
@@ -1243,6 +1244,8 @@ unsigned StringTableSection::addString(StringRef s, bool hashIt) {
     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);
@@ -2155,7 +2158,7 @@ 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)});
 }
 
diff --git a/lld/docs/ReleaseNotes.rst b/lld/docs/ReleaseNotes.rst
index f7e099b..f3358c8 100644
--- a/lld/docs/ReleaseNotes.rst
+++ b/lld/docs/ReleaseNotes.rst
@@ -33,6 +33,9 @@ ELF Improvements
   (`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:
 
diff --git a/lld/test/ELF/strtab-dedup.s b/lld/test/ELF/strtab-dedup.s
new file mode 100644
index 0000000..e7c36a4
--- /dev/null
+++ b/lld/test/ELF/strtab-dedup.s
@@ -0,0 +1,33 @@
+# 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