[lld/mac] Give range extension thunks for local symbols local visibility

[thakis]

Summary

When two local symbols (think: file-scope static functions, or functions in
unnamed namespaces) with the same name in two different translation units
both needed thunks, ld64.lld previously created external thunks for both
of them. These thunks ended up with the same name, leading to a duplicate
symbol error for the thunk symbols.

Instead, give thunks for local symbols local visibility.

(Hitting this requires a jump to a local symbol from over 128 MiB away.
It's unlikely that a single .o file is 128 MiB large, but with ICF
you can end up with a situation where the local symbol is ICF'd with
a symbol in a separate translation unit. And that can introduce a
large enough jump to require a thunk.)

Fixes PR54599.

[thakis]

update more comments

[int3]

Nice!

Can you include a bit more info in the commit message? Would be nice if people didn't have to click through to the PR

lld/MachO/ConcatOutputSection.cpp

92–93

nit: reflow paragraph?

lld/test/MachO/arm64-thunk-visibility.s

4

ultra nit: not sure if you intended to use one dot or three :p

[thakis]

Landed with much more detailed commit message. Thanks!

lld/MachO/ConcatOutputSection.cpp

 //     multiple thunks to the same destination distributed throughout a large
 //     program so that all call sites can have one within range.
 //
 // The optimal approach is to mix islands for destinations within two hops,
 // and use thunks for destinations at greater distance. For now, we only
 // implement thunks. TODO: Adding support for branch islands!
 //
 // Internally -- as expressed in LLD's data structures -- a
-// branch-range-extension thunk comprises ...
+// branch-range-extension thunk consists of:
 //
-// (1) new Defined privateExtern symbol for the thunk named
+// (1) new Defined symbol for the thunk named
 //     <FUNCTION>.thunk.<SEQUENCE>, which references ...
 // (2) new InputSection, which contains ...
 // (3.1) new data for the instructions to load & branch to the far address +
 // (3.2) new Relocs on instructions to load the far address, which reference ...
-// (4.1) existing Defined extern symbol for the real function in __text, or
+// (4.1) existing Defined symbol for the real function in __text, or
 // (4.2) existing DylibSymbol for the real function in a dylib
 //
 // Nearly-optimal thunk-placement algorithm features:
 //
 // * Single pass: O(n) on the number of call sites.
 //
 // * Accounts for the exact space overhead of thunks - no heuristics
 //
 // * Exploits the full range of call instructions - forward & backward
 //
 // Data:
 //
 // * DenseMap<Symbol *, ThunkInfo> thunkMap: Maps the function symbol
 //   to its thunk bookkeeper.
 //
 // * struct ThunkInfo (bookkeeper): Call instructions have limited range, and
 //   distant call sites might be unable to reach the same thunk, so multiple
 //   thunks are necessary to serve all call sites in a very large program. A
 //   thunkInfo stores state for all thunks associated with a particular
 //   function: (a) thunk symbol, (b) input section containing stub code, and
 //   (c) sequence number for the active thunk incarnation. When an old thunk
 //   goes out of range, we increment the sequence number and create a new
 //   thunk named <FUNCTION>.thunk.<SEQUENCE>.
 //
-// * A thunk incarnation comprises (a) private-extern Defined symbol pointing
-//   to (b) an InputSection holding machine instructions (similar to a MachO
+// * A thunk consists of (a) a Defined symbol pointing to
+//   (b) an InputSection holding machine instructions (similar to a MachO
 //   stub), and (c) Reloc(s) that reference the real function for fixing-up
 //   the stub code.
 //
 // * std::vector<InputSection *> MergedInputSection::thunks: A vector parallel
 //   to the inputs vector. We store new thunks via cheap vector append, rather
 //   than costly insertion into the inputs vector.
 //
 // Control Flow:
for (Reloc &r : reverse(relocs)) {
 
       // This code runs after dead code removal. Need to set the `live` bit
       // on the thunk isec so that asserts that check that only live sections
       // get written are happy.
       thunkInfo.isec->live = true;
 
       StringRef thunkName = saver().save(funcSym->getName() + ".thunk." +
                                          std::to_string(thunkInfo.sequence++));
+      if (!isa<Defined>(funcSym) || cast<Defined>(funcSym)->isExternal()) {
         r.referent = thunkInfo.sym = symtab->addDefined(
             thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0,
-          /*size=*/thunkSize, /*isWeakDef=*/false, /*isPrivateExtern=*/true,
+            thunkSize, /*isWeakDef=*/false, /*isPrivateExtern=*/true,
             /*isThumb=*/false, /*isReferencedDynamically=*/false,
             /*noDeadStrip=*/false, /*isWeakDefCanBeHidden=*/false);
+      } else {
+        r.referent = thunkInfo.sym = make<Defined>(
+            thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0,
+            thunkSize, /*isWeakDef=*/false, /*isExternal=*/false,
+            /*isPrivateExtern=*/true, /*isThumb=*/false,
+            /*isReferencedDynamically=*/false, /*noDeadStrip=*/false,
+            /*isWeakDefCanBeHidden=*/false);
+      }
       thunkInfo.sym->used = true;
       target->populateThunk(thunkInfo.isec, funcSym);
       finalizeOne(thunkInfo.isec);
       thunks.push_back(thunkInfo.isec);
       ++thunkCount;
     }
   }
   size = isecAddr - addr;

lld/test/MachO/arm64-thunk-starvation.s

 _f3: b _fn3
 _f4: b _fn4
 _f5: b _fn5
 _f6: b _fn6
 ## 6 * 4 = 24 bytes for branches
 ## Currently leaves 12 bytes for one thunk, so 36 bytes.
 ## Uses < instead of <=, so 40 bytes.
 
-.global _spacer1, _spacer1
+.global _spacer1, _spacer2
 ## 0x8000000 is 128 MiB, one more than the forward branch limit,
 ## distributed over two functions since our thunk insertion algorithm
 ## can't deal with a single function that's 128 MiB.
 ## We leave just enough room so that the old thunking algorithm finalized
 ## both spacers when processing _f1 (24 bytes for the 4 bytes code for each
 ## of the 6 _f functions, 12 bytes for one thunk, 4 bytes because the forward
 ## branch range is 128 Mib - 4 bytes, and another 4 bytes because the algorithm
 ## uses `<` instead of `<=`, for a total of 44 bytes slop.) Of the slop, 20

lld/test/MachO/arm64-thunk-visibility.s

+# REQUIRES: aarch64
+
+# foo.s and bar.s both contain TU-local symbols (think static function)
+# with the same name, and both need a thunk..  This tests that ld64.lld doesn't
+# create a duplicate symbol for the two functions.
+
+# Test this both when the TU-local symbol is the branch source or target,
+# and for both forward and backwards jumps.
+
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/foo.s -o %t/foo.o
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/bar.s -o %t/bar.o
+# RUN: %lld -arch arm64 -lSystem -o %t.out %t/foo.o %t/bar.o
+
+#--- foo.s
+
+.subsections_via_symbols
+
+# Note: No .globl, since these are TU-local symbols.
+.p2align 2
+_early_jumping_local_fn: b _some_late_external
+.p2align 2
+_early_landing_local_fn: ret
+
+.globl _some_early_external
+.p2align 2
+_some_early_external: b _late_landing_local_fn
+
+## 0x8000000 is 128 MiB, one more than the forward branch limit.
+## Distribute that over two functions since our thunk insertion algorithm
+## can't deal with a single function that's 128 MiB.
+.global _spacer1, _spacer2
+_spacer1:
+.space 0x4000000
+_spacer2:
+.space 0x4000000
+
+# Note: No .globl, since these are TU-local symbols.
+.p2align 2
+_late_jumping_local_fn: b _some_early_external
+.p2align 2
+_late_landing_local_fn: ret
+
+.globl _some_late_external
+.p2align 2
+_some_late_external: b _early_landing_local_fn
+
+#--- bar.s
+
+.subsections_via_symbols
+
+# Note: No .globl, since these are TU-local symbols.
+.p2align 2
+_early_jumping_local_fn: b _some_other_late_external
+.p2align 2
+_early_landing_local_fn: ret
+
+.globl _some_other_early_external
+.p2align 2
+_some_other_early_external: b _late_landing_local_fn
+
+## 0x8000000 is 128 MiB, one more than the forward branch limit.
+## Distribute that over two functions since our thunk insertion algorithm
+## can't deal with a single function that's 128 MiB.
+.global _other_spacer1, _other_spacer1
+_spacer1:
+.space 0x4000000
+_spacer2:
+.space 0x4000000
+
+# Note: No .globl, since these are TU-local symbols.
+.p2align 2
+_late_jumping_local_fn: b _some_other_early_external
+.p2align 2
+_late_landing_local_fn: ret
+
+.globl _some_other_late_external
+.p2align 2
+_some_other_late_external: b _early_landing_local_fn
+
+.globl _main
+_main:
+  ret