[lld-macho] Don't emit symbols into the symtab multiple times

[lgrey]

Summary

https://reviews.llvm.org/D139069 made the entry in symbols for private aliases point directly to the aliasee. This caused a new symbol table entry to be created for the aliasee each time it appeared in symbols which

• Increases the number of symbols emitted (since the private aliases wouldn't have been emitted as their own symbol)
• Confuses dsymutil, which says stuff like:

<snip>
warning: (x86_64)  failed to insert symbol '_.str.422' in the debug map.
warning: (x86_64)  failed to insert symbol '_.str.423' in the debug map.
warning: (x86_64)  failed to insert symbol '_.str.424' in the debug map.
warning: (x86_64)  failed to insert symbol '_.str.425' in the debug map.
warning: (x86_64)  failed to insert symbol '_.str.426' in the debug map.
<snip>

This change adds all symbols that have already been added to a set and checks against it to decide whether to add a symbol or not, which has a little bit of overhead (Chromium's base_unittests in ASAN configuration; as one might assume the difference is dwarfed in LTO builds). Not sure if this is significant enough to drop this approach and try something more complex.

+------------------------------------------------------------+
|              x                           +             +   |
|x             *             x             +             +   |
|    |_________A_________|                                   |
|                         |________________A________________||
+------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x   5          1.28           1.3          1.29          1.29  0.0070710678
+   5          1.29          1.32          1.31          1.31   0.012247449
Difference at 95.0% confidence
	0.02 +/- 0.0145844
	1.55039% +/- 1.13058%
	(Student's t, pooled s = 0.01)

[int3]

1.5% seems kinda significant. I wonder if I should rethink my approach in D139069... let me try some things

lld/test/MachO/private-label-alias.s

69

[lgrey]

In D144589#4148422, @int3 wrote:

1.5% seems kinda significant.

FWIW, the margin of error is pretty big, so I'm not sure how real it is. If the other stuff you try out isn't promising, I can try rerunning with a bigger n.

[lgrey]

Ping :) Have you had a chance to think about alternatives?

[int3]

Yeah sorry been a bit swamped but I'll try to put up something by Monday. Basically my plan is to sort the symbols such that weak defs appear after all other definitions, so that when we do weak def coalescing we can bring along all the other local symbols as well. I think it should work, just a matter of how messy the implementation is...

[int3]

As promised: D145455: [lld-macho] Coalesce local symbol aliases along with their aliased weak def

Unfortunately I am traveling this week and don't have access to my usual benchmarking machine, so I can't run the numbers, but I think my change should add minimal overhead.

I can do the benchmarks at the EOW and land this then

[int3]

Turns out D145455: [lld-macho] Coalesce local symbol aliases along with their aliased weak def is a massive perf win because the old 'solution' was actually a perf regression... heh

[lgrey]

Obviated by https://reviews.llvm.org/D145455

lld/MachO/SyntheticSections.cpp

 #include "lld/Common/CommonLinkerContext.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/xxhash.h"
 
 #if defined(__APPLE__)
 #include <sys/mman.h>
 
 #define COMMON_DIGEST_FOR_OPENSSL
 #include <CommonCrypto/CommonDigest.h>
 #else
for (SortingPair &pair : symbolsNeedingStabs) {
     }
   }
 
   if (!stabs.empty())
     emitEndSourceStab();
 }
 
 void SymtabSection::finalizeContents() {
+  SmallPtrSet<const Symbol*, 8> seenSymbols;
   auto addSymbol = [&](std::vector<SymtabEntry> &symbols, Symbol *sym) {
+    if (seenSymbols.insert(sym).second != true)
+      return;
     uint32_t strx = stringTableSection.addString(sym->getName());
     symbols.push_back({sym, strx});
   };
 
   std::function<void(Symbol *)> localSymbolsHandler;
   switch (config->localSymbolsPresence) {
   case SymtabPresence::All:
     localSymbolsHandler = [&](Symbol *sym) { addSymbol(localSymbols, sym); };

lld/test/MachO/private-label-alias.s

 ## specified. We don't. But again, given how rare the lack of that directive is
 ## (I've only seen it from hand-written assembly inputs), I don't think we need
 ## to worry about it.
 
 # RUN: rm -rf %t; split-file %s %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/weak-then-private.s -o %t/weak-then-private.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/private-then-weak.s -o %t/private-then-weak.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/no-dead-strip.s -o %t/no-dead-strip.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/all-local.s -o %t/all-local.o
 # RUN: %lld -dylib %t/weak-then-private.o %t/private-then-weak.o -o %t/test1
 # RUN: %lld -dylib %t/private-then-weak.o %t/weak-then-private.o -o %t/test2
 # RUN: %lld -dead_strip %t/no-dead-strip.o -o %t/no-dead-strip
+# RUN: %lld -dylib %t/all-local.o -o %t/all-local
 
 # RUN: llvm-objdump --macho --syms --section="__DATA,__data" --weak-bind %t/test1 | FileCheck %s
 # RUN: llvm-objdump --macho --syms --section="__DATA,__data" --weak-bind %t/test2 | FileCheck %s
 
 ## Check that we only have one copy of 0x123 in the data, not two.
 # CHECK:       Contents of (__DATA,__data) section
 # CHECK-NEXT:  0000000000001000  23 01 00 00 00 00 00 00 00 10 00 00 00 00 00 00 {{$}}
 # CHECK-NEXT:  0000000000001010  00 10 00 00 00 00 00 00 {{$}}

 ## Verify that we don't drop any flags that private-label aliases have (such as
 ## .no_dead_strip). This is a regression test. We previously had subsections
 ## that were mistakenly stripped.
 
 # RUN: llvm-objdump --macho --section-headers %t/no-dead-strip | FileCheck %s \
 # RUN:   --check-prefix=NO-DEAD-STRIP
 # NO-DEAD-STRIP: __data        00000010
 
+## Ensure that a private alias to a local label doesn't write two identical
+## entries to the symbol table.
+# RUN: llvm-objdump --macho --syms %t/all-local | FileCheck %s --check-prefix=NO-DUPES
+# NO-DUPES: SYMBOL TABLE:
+# NO-DUPES-NEXT: 00000000000002c8 l     F __TEXT,__text _label
+# NO-DUPES-NEXT: 00000000000002d0 l     F __TEXT,__text _ref
+
 #--- weak-then-private.s
 .globl _weak
 .weak_definition _weak
 .data
 _weak:
 l_ignored:
   .quad 0x123
 

 l_foo:
   .quad 0x123
 
 l_bar:
 _bar:
   .quad 0x123
 
 .subsections_via_symbols
+
+#--- all-local.s
+.text
+
+l_ignored:
+_label:
+  .quad 0x123
+
+_ref:
+  .quad l_ignored
+
+.subsections_via_symbols