[LLD, Mach-O] RFC: A Flexible Multi-pass Algorithm for Branch-Range Extension
Summary
This RFC proposes a flexible, multipass algorithm for resolving out-of-range ARM64 branches in LLD’s Mach-O port. The algorithm eliminates fixed slop reservations. It uses compact 4-byte islands for most out-of-range branches and 12-byte thunks for branches that require greater reach.
Each extender type has a configurable hop limit. The planner tries extender types in order of increasing reach, using a single type throughout each route. If it cannot construct a route within that type’s hop limit, it tries the next type. If no enabled type can form a route, linking fails.
For ARM64, -arm64-islands-max-hops defaults to 2, and -arm64-thunks-max-hops defaults to 1. Setting either limit to zero disables that extender type.
Motivation
LLD’s Mach-O port currently uses a single-pass finalizer that resolves every out-of-range branch with a 12-byte thunk. These thunks can reach any target in a __TEXT segment smaller than 4 GiB, which is sufficient in most cases. The finalizer pessimistically reserves slop to keep every call-to-thunk branch in range as later insertions shift the layout. This reservation reduces the usable branch range. If it is insufficient, users must work around thunk-range overruns by tuning --=slop_scale. This need for manual tuning results in a poor user experience.
Although thunks generally provide sufficient reach, islands offer two key advantages: they preserve the x16 register and use less space when the __TEXT segment is smaller than roughly 384 MiB. Two island hops are generally enough to cover branches in binaries of this size. We therefore propose a slop-free hybrid that favors islands and falls back to thunks after a configurable number of hops.
Results
We evaluated two production binaries: App1, with a 456.05 MiB __TEXT segment, and App2, with a 449.16 MiB __TEXT segment. We linked each binary using four configurations: the current Mach-O thunk strategy, ld64-style islands, and the proposed algorithm with maxHops=inf and maxHops=2. Contribution is the total size of the emitted extender code: 4 bytes per island and 12 bytes per thunk.
Here, maxHops=inf denotes -arm64-islands-max-hops 4294967295 and maxHops=2 denotes -arm64-islands-max-hops 2. The benchmark charts use max-hops=2 and max-hops=inf for the same proposed configurations.
| Configuration | x16 clobber |
Slop-free | App1 contribution | App2 contribution |
|---|---|---|---|---|
current Mach-O thunks |
yes | no | 3.68 MiB | 6.38 MiB |
ld64-style islands |
no | no | 1.83 MiB | 3.99 MiB |
maxHops=inf |
on fallback | yes | 1.75 MiB | 3.29 MiB |
maxHops=2 |
on fallback | yes | 1.75 MiB | 3.69 MiB |
The x16 column describes extender behavior: islands preserve x16, while fallback thunks clobber it. Neither proposed configuration emits thunks in App1; only maxHops=2 emits thunks in App2. Even with unlimited hops, thunk fallback remains available if an island route cannot be formed. The corresponding extender counts are:
| Configuration | App1 thunks | App1 islands | App2 thunks | App2 islands |
|---|---|---|---|---|
current Mach-O thunks |
321,574 | 0 | 557,250 | 0 |
ld64-style islands |
0 | 478,440 | 0 | 1,046,355 |
maxHops=inf |
0 | 457,498 | 0 | 863,343 |
maxHops=2 |
0 | 457,498 | 73,884 | 746,841 |
Two island hops cover all call distances in App1, so maxHops=2 and maxHops=inf produce the same extender counts and contribution. App2 contains calls that require more than two island hops; with maxHops=2, those calls use thunks instead.
Runtime performance
App1 launch time:
App1 page-in events:
App2 launch time:
App2 page-in events:
Linking performance
App1 finalization benchmark: 3 warm-up followed by 20 consecutive measured runs
App2 finalization benchmark: 3 warm-up followed by 20 consecutive measured runs.
Benchmark Summary
The default maxHops=2 configuration trades longer finalization time for smaller extender code and lower measured mean launch times than the current Mach-O thunk strategy.
Unlimited hops minimize extender code size among the measured configurations, while maxHops=2 has lower mean launch times in both apps and a lower mean finalization time in App2. These results favor maxHops=2 as a balance between code size and performance, with unlimited hops offering an additional size benefit in App2.
Proposed algorithm
Like ELF, we use multiple passes because inserting branch extenders shifts later addresses and may push other branches out of range. Our algorithm has three main features: replanning extender routes each round, callee-guided planning for extender reuse, and a preference for a coarse subset of placement boundaries—the insertion points after InputSection.
Replan each round
The current Mach-O finalizer use estimated slop so it never repairs unreachable branches; underestimation can require manual tuning. ELF instead repairs unreachable branches across passes, often by creating a thunk closer to the caller. Long-range thunks make this local repair practical.
Multi-hop island chains couple more constraints: moving an island can break adjacent links or shared routes, while adding an island can exceed the hop limit. We therefore retain learned space requirements across rounds, but discard failed routes and placements.
Each boundary tracks a reservedSize estimate. When a proposal is invalid, we update these estimates and rebuild complete routes against the revised layout, within the configured hop limit. This replaces fixed slop with iterative space feedback and avoids repairing existing chains, at the cost of replanning routes that were already valid.
Callee-guided planning
To construct island chains within the exact configured hop limit, we resolve each callee’s address against the current planning layout. We group callsites by callees so that callers share this target information and the extenders built for it. Processing them together keeps accesses to shared route state localized, which can make planning more cache-friendly. This locality comes at the cost of preprocessing and additional storage for the caller groups.
Within each group, we process callers on each side of the callee from farthest to nearest, reusing reachable extenders before constructing new routes. For islands, we construct a complete chain from the callee outward toward the caller, subject to the hop limit. Subsequent nearer callers reuse the innermost reachable island, sharing the remaining route without unnecessary hops.
Prefer coarse boundaries
When placing an extender, we first search a coarse subset of boundaries between input sections. If no coarse candidate is usable, we search all boundaries. This concentrates extender code at shared insertion points to improve code locality, while allowing finer placement when needed.
The backend configures the spacing of coarse boundaries. For ARM64, -arm64-branch-extension-coarse-boundary-spacing accepts a byte count from 0 through 4294967295 and defaults to 1048576 (1 MiB). Zero includes every input boundary in the coarse catalog.





