[lld-macho] Account for alignment in thunk insertion algorithm

[int3]

Summary

We previously neglected this, leading us to underestimate the maximum
possible branch address offset.

Fixing this should allow us to reduce slop to more reasonable
levels. I've lowered it to 256 for now, though I suspect we could go
lower.

Fixes https://github.com/llvm/llvm-project/issues/59259.

[int3]

update

[serge-sans-paille]

Thanks for providing a much more satisfying approach than the one I proposed in https://reviews.llvm.org/D144020 !

[int3]

Sorry it took a while for me to get to fixing this -- been busy. Thanks for the review!

[DavidSpickett]

Some tests started failing on 32 bit here, the usual thing I think. Fixed in https://github.com/llvm/llvm-project/commit/0e1fb48bb95abaf94c0d21b58c4c075f6faad8ba, please correct if this was not your intent.

[int3]

Oops. Thanks for the fix!

[thakis]

Noticed this while looking through commits. Great catch, thanks much! :)

lld/MachO/ConcatOutputSection.cpp

for (size_t callIdx = 0, endIdx = inputs.size(); callIdx < endIdx;
 
     // Assign addresses up-to the forward branch-range limit.
     // Every call instruction needs a small number of bytes (on Arm64: 4),
     // and each inserted thunk needs a slightly larger number of bytes
     // (on Arm64: 12). If a section starts with a branch instruction and
     // contains several branch instructions in succession, then the distance
     // from the current position to the position where the thunks are inserted
     // grows. So leave room for a bunch of thunks.
-    unsigned slop = 1024 * thunkSize;
-    while (finalIdx < endIdx && addr + size + inputs[finalIdx]->getSize() <
-                                    isecVA + forwardBranchRange - slop)
+    unsigned slop = 256 * thunkSize;
+    while (finalIdx < endIdx) {
+      size_t expectedNewSize = alignTo(addr + size, inputs[finalIdx]->align) +
+                               inputs[finalIdx]->getSize();
+      if (expectedNewSize >= isecVA + forwardBranchRange - slop)
+        break;
       finalizeOne(inputs[finalIdx++]);
+    }
 
     if (!isec->hasCallSites)
       continue;
 
     if (finalIdx == endIdx && stubsInRangeVA == TargetInfo::outOfRangeVA) {
       // When we have finalized all input sections, __stubs (destined
       // to follow __text) comes within range of forward branches and
       // we can estimate the threshold address after which we can

lld/test/MachO/arm64-thunk-for-alignment.s

+# REQUIRES: aarch64
+# 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 -dylib -arch arm64 -lSystem -o %t/out %t/foo.o %t/bar.o
+
+# RUN: llvm-objdump --macho --syms %t/out | FileCheck %s
+# CHECK: _bar.thunk.0
+
+## Regression test for PR59259. Previously, we neglected to check section
+## alignments when deciding when to create thunks.
+
+## If we ignore alignment, the total size of _spacer1 + _spacer2 below is just
+## under the limit at which we attempt to insert thunks between the spacers.
+## However, with alignment accounted for, their total size ends up being
+## 0x8000000, which is just above the max forward branch range, making thunk
+## insertion necessary. Thus, not accounting for alignment led to an error.
+
+#--- foo.s
+
+_foo:
+  b _bar
+
+## Size of a `b` instruction.
+.equ callSize, 4
+## Refer to `slop` in TextOutputSection::finalize().
+.equ slopSize, 12 * 256
+
+_spacer1:
+  .space 0x4000000 - slopSize - 2 * callSize - 1
+
+.subsections_via_symbols
+
+#--- bar.s
+.globl _bar
+
+.p2align 14
+_spacer2:
+  .space 0x4000000
+
+_bar:
+  ret
+
+.subsections_via_symbols