[lld/mac] Leave more room for thunks in thunk placement code

[thakis]

Summary

Fixes PR51578 in practice.

Currently there's only enough room for a single thunk, which for real-life code
isn't enough. The error case only happens when there are many branch statements
very close to each other (0 or 1 instructions apart), with the function at the
finalization barrier small.

There's a FIXME on what to do if we hit this case, but that suggestion sounds
complicated to me (see end of PR51578 comment 5 for why).

Instead, just leave more room for thunks. Chromium's unit_tests links fine with
room for 3 thunks. Leave room for 100, which should fix this for most cases in
practice.

There's little cost for leaving lots of room: This slop value only determines
when we finalize sections, and we insert thunks for forward jumps into
unfinalized sections. So leaving room means we'll need a few more thunks, but
the thunk jump range is 128 MiB while a single thunk is just 12 bytes.

For Chromium's unit_tests:
With a slop of 3: thunk calls = 355418, thunks = 10903
With a slop of 100: thunk calls = 355426, thunks = 10904

Chances are 100 is enough for all use cases we'll hit in practice, but even
bumping it to 1000 would probably be fine.

[thakis]

rebase?

[int3]

lgtm. I suppose it's a bit too awkward to unit test?

lld/MachO/ConcatOutputSection.cpp

242

I'm confused about why the number of bytes for a call instruction is relevant here, since the call instruction will always be present regardless of whether the thunk is inserted

[thakis]

I thought it'd be awkward to test, but it actually wasn't. Added a test.

Thanks for the review!

lld/MachO/ConcatOutputSection.cpp

242

What matters is the distance to the instruction after the call instruction. If there are at least 12 bytes between call instructions, all's well. Since we're at a call instruction, there are guaranteed to be at least 4 bytes until the next call instruction. So we lose 8 bytes for every two directly consecutive calls.

lld/MachO/ConcatOutputSection.cpp

void ConcatOutputSection::finalize() {
   uint64_t backwardBranchRange = target->backwardBranchRange;
   uint64_t stubsInRangeVA = TargetInfo::outOfRangeVA;
   size_t thunkSize = target->thunkSize;
   size_t relocCount = 0;
   size_t callSiteCount = 0;
   size_t thunkCallCount = 0;
   size_t thunkCount = 0;
 
+  // Walk all sections in order. Finalize all sections that are less than
+  // forwardBranchRange in front of it.
+  // isecVA is the address of the current section.
+  // isecAddr is the start address of the first non-finalized section.
+
   // inputs[finalIdx] is for finalization (address-assignment)
   size_t finalIdx = 0;
   // Kick-off by ensuring that the first input section has an address
   for (size_t callIdx = 0, endIdx = inputs.size(); callIdx < endIdx;
        ++callIdx) {
     if (finalIdx == callIdx)
       finalizeOne(inputs[finalIdx++]);
     ConcatInputSection *isec = inputs[callIdx];
     assert(isec->isFinal);
     uint64_t isecVA = isec->getVA();
-    // Assign addresses up-to the forward branch-range limit
+
+    // 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 slighly 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 = 100 * thunkSize;
     while (finalIdx < endIdx && isecAddr + inputs[finalIdx]->getSize() <
-                                    isecVA + forwardBranchRange - thunkSize)
+                                    isecVA + forwardBranchRange - slop)
       finalizeOne(inputs[finalIdx++]);
+
     if (isec->callSiteCount == 0)
       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
       // reach any stub with a forward branch. Note that although it
       // sits in the middle of a loop, this code executes only once.
       // It is in the loop because we need to call it at the proper
       // time: the earliest call site from which the end of __text
for (Reloc &r : reverse(relocs)) {
         uint64_t thunkVA = thunkInfo.isec->getVA();
         if (lowVA <= thunkVA && thunkVA <= highVA) {
           r.referent = thunkInfo.sym;
           continue;
         }
       }
       // ... otherwise, create a new thunk.
       if (isecAddr > highVA) {
-        // When there is small-to-no margin between highVA and
-        // isecAddr and the distance between subsequent call sites is
-        // smaller than thunkSize, then a new thunk can go out of
-        // range.  Fix by unfinalizing inputs[finalIdx] to reduce the
-        // distance between callVA and highVA, then shift some thunks
-        // to occupy address-space formerly occupied by the
-        // unfinalized inputs[finalIdx].
+        // There were too many consecutive branch instructions for `slop`
+        // above. If you hit this: For the current algorithm, just bumping up
+        // slop above and trying again is probably simplest. (See also PR51578
+        // comment 5).
         fatal(Twine(__FUNCTION__) + ": FIXME: thunk range overrun");
       }
       thunkInfo.isec =
           make<ConcatInputSection>(isec->getSegName(), isec->getName());
       thunkInfo.isec->parent = this;
 
       // 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