[LLD, Mach-O] RFC: A Flexible Multipass Algorithm for Branch-Range Extension

[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.

Related PR

3 Likes

Thanks for the RFC! This is a critical optimization for apps larger than 128MB, and I know the current implementation could be improved. The two main points being 1) removing --slop-scale, 2) using branch islands, and maybe 3) reducing thunks to stubs (see TextOutputSection::estimateStubsEndVA()). I’ve left some thoughts below.

Branch-range extensions are only needed for Arm64, but this proposal sounds like it is meant to be more general. For example, why do we have the -arm64-{islands,thunk}-max-hops options? If a branch requires more than 2 hops, it is more efficient to use a 3 instruction thunk.

Our branch extension algorithm should not fail the link. This is the main pain point of the existing --slop-scale option: if the algorithm runs out of space, we hit the fatal error below.

The only reason I can think of where a branch extension algorithm would fail the link is if the branch target is out of range of even a thunk. I believe this happens after ±4GB because addresses can no longer be resolved via adrp/add. But I feel like we would have bigger problems in that case, and I don’t know of another way to extend a branch further.

LLD runs after register allocation, so LLD does not do any liveness analysis. The exception being x16 and x17 which are left available as scratch registers for function calls. Therefore there isn’t really an advantage to avoid clobbering x16.

In the first table, is “App1 contribution” the bytes that come from thunks alone? If so, 3.68 MiB is suspiciously large. Are you building on the latest LLVM? [lld][MachO] Deduplicate branch-extension thunks for ICF-folded symbols by nocchijiang · Pull Request #185396 · llvm/llvm-project · GitHub recently fixed a bug and we saw a 1% binary size improvement from that PR alone. I also have a few more recent PRs that improved the algorithm to reduce overhead.

It looks like maxHops=2 produces more overhead for App2 than just using branch-islands. Ideally the algorithm would automatically select the extension type that would yield the smallest binary size. If using thunks increases the size overhead, why not use branch-islands only?

And thanks for measuring linking performance. This is another concern, albeit less important than binary size IMO. Have you also measured memory usage? LLD is interesting in that it doesn’t deallocate memory until the program exits. This means we need to be careful with our heap usage for long running algorithms.

2 Likes

Hi Ellis, thanks for the detailed review! Xiaoyang (@KotoriAster) wrapped up his internship this week, so I’ll be following up on the RFC and the PR from here on.

We did design the planner to be target-independent; the extender types and their hop limits come from the backend, and ARM64 is just the only Mach-O target that needs them today. We’ve also seen recent interest in unifying branch-range extension across the LLD ports. We didn’t go that far in the prototype, but I think the design could grow in that direction.

On efficiency: you’re right that a thunk wins over 3+ island hops in pure size. The reason we allow unbounded island chains is that some of our apps need to be islands all the way down. They link inputs that don’t follow the ABI (they rely on x16/x17 being preserved across calls), and we have zero control over those inputs. This is also my answer to your register allocation point.

I think the wording in the RFC made this sound more likely than it is. We put real effort into trying to break it, including using an LLM to help construct a failing repro, and we couldn’t produce one. Removing this kind of user hassle (--slop-scale today) was a core goal of the design.

We tested on a downstream branch with the relevant patches backported, including #185396. The numbers are large because we enabled aggressive compile-time global optimizations, which produce many frequently-called functions spread across __text. We did this on purpose to make the long-branch situation worse, so the effect of the new algorithm would be easier to see. With this setup, the binary can’t even link with an ld64-style fixed 4 MiB island region, without the ICF fix.

As mentioned above, for our own apps we plan to use unlimited island hops with thunks disabled to cope with the ABI-breaking inputs. The defaults (2 island hops, 1 thunk hop) are meant to be a sweet spot for typical inputs that weren’t built with aggressive optimizations like ours. YMMV, and the knobs are there so users can tune for their own binaries, including adjusting the coarse boundary spacing to get behavior closer to ld64.

Not yet. As far as I know, we reclaim most if not all of the temporary memory allocated while the algorithm runs. Slightly off-topic, but LLD’s approach of not freeing memory until exit is a tradeoff I’m not a big fan of. Linking App1/App2 takes more than 30 GB, and on some of our build bots with less memory (not to mention current memory prices), this causes heavy swapping that actually slows the link down. I understand why LLD makes this tradeoff, but I think it needs a better balance point today.

3 Likes

I’ve tested the PR you linked on two of our apps which are large enough to require branch-range extensions. I haven’t looked at the code yet, but they appear to build fine and I haven’t seen any crashes while running them. For both apps I saw ~0.15% uncompressed size win, which is about 800 KiB.

When you are ready to publish the PR, I’d be happy to help review it. It does look like a pretty large PR in a tricky part of LLD, so I imagine it will take time to review. Would you consider splitting it into smaller PRs?

Thanks for testing it on your apps, Ellis! It’s great to hear that both linked cleanly and that you saw a size win on your side as well.

On splitting: I’m afraid there isn’t much room to break it down. The main part, the planner itself, is unavoidably large, and some of the refactoring in this PR can’t be landed separately because the planner depends on it. For example, we removed TextOutputSection entirely. Whether an output section got the thunk treatment depended purely on its segment/section name, which was fragile. The old algorithm also handled multiple code-bearing output sections and flexible section ordering poorly. The new design classifies sections by whether they actually contain branch relocations and plans extenders per OutputSegment, so that layout change and the planner have to go in together.

I thought the PR was mostly ready for review as is. But if you’d prefer a gradual landing plan, let’s discuss it here first. Once we agree on one, I’ll restructure the PR to follow it.

Thanks for working on this!

We (well, Liza) measured this on Chromium, and we couldn’t see any launch time improvements. Do we have to do anything special to be able to do this?

Also, the PR as-is seems to make link time worse (something we’re trying to improve at the moment ( Plan to improve ld64.lld performance ), and it seems to be harder to make concurrent. (We have a few commits that speed up the current approach a good bit; we tried speeding up this approach similarly and came short.)

Thanks for testing this on Chromium!

If you’re not seeing launch time benefits, my guess is that either you’re not building with aggressive code size optimizations, or your order file is already of very high quality. Our builds use very aggressive optimizations that introduce a large number of calls to shared helpers, most of them outlined functions. We have a downstream patch that automatically pulls shared helpers called from the ordered region into that region (I believe @ellishg’s team has something similar). Even with that targeted effort, our apps show noticeable run-to-run variance, and we can’t get an order file good enough to cover every branch. The code paths that leak out of the ordered region make startup page faults significantly worse, and that is where a better branch extension algorithm stands out.

On link time: yes, I’m aware of your effort and we take it seriously too. We actually spent a couple of weeks tuning link-time performance before publishing the RFC. I suspect the most noticeable overhead comes from the mandatory relocation scan before planning. The algorithm itself doesn’t strictly need it; we added it because the current logic decides which output sections can contain code purely based on section names, which is fragile.

I’ll profile this on the repro tarballs you published in #222068. Which one exactly did Liza measure? I want to make sure I’m looking at the same link you are. Once I have numbers, I’ll follow up here on splitting out the scan and on improving concurrency.

@nocchijiang I tested on the mac_rel_static_sym_1 and mac_rel_static_sym_0 since they’re both release builds.

Just for reference here’s a couple hyperfine runs from mac_rel_static_sym_1 that I got

ToT
Time (mean ± σ):      5.597 s ±  0.095 s    [User: 6.226 s, System: 3.776 s]
Range (min … max):    5.495 s …  5.853 s    20 runs

thunk-islands
Time (mean ± σ):      5.134 s ±  0.023 s    [User: 6.330 s, System: 3.855 s]
Range (min … max):    5.105 s …  5.177 s    20 runs

pr-232218
Time (mean ± σ):      6.179 s ±  0.182 s    [User: 7.266 s, System: 3.755 s]
Range (min … max):    5.971 s …  6.619 s    20 runs

pr-232218-patched
Time (mean ± σ):      5.381 s ±  0.171 s    [User: 6.951 s, System: 3.725 s]
Range (min … max):    5.213 s …  5.831 s    20 runs

The thunk-islands change refers to a prototype I have been working on here and pr-232218-patched refers to a quick and dirty prototype I tried out with an LLM to see if there were any link time performance improvements I could get, that’s here. Note: I’ve paused upstreaming the thunk-islands branch based on this RFC, but I’ve reviewed it pretty well so am more confident in it, but the latter prototype based off your PR I haven’t done much more than skim yet to get a sense of how the LLM fine tuned improvements, I’m mostly just sharing it as a reference as I did at least some immediate link-time performance improvements.

There’s a few different parallelizations that that prototype does, and I admittedly am not entirely sure how it might affect run time performance since I don’t have a binary to test that with. My initial assessment is that it might not regress runtime performance because it looks like it’s still searching the same coarse boundaries and grouping thunks into the same islands as your PR. But my overall feeling is that while I think the PR that goes with this RFC is regressing link time performance, I do think there’s space to tune link-time performance on top of your PR in future changes.

2 Likes

Hi Liza, Thanks for the link time improvement prototype.

In our previous optimization work, we mainly relied on human analyzing sampling profiles rather than handing the work over to LLM, because we knew this would be a huge diff that is hard to review, and we tried to keep it readable. This time I also gave code agent a try, and I now have a version that matches your thunk-islands prototype link time wise, while keeping output byte-identical to our current branch. The same changes make Finalize addresses about 5-6x faster than our previous version on our in-house workloads, which are the same App1 and App2 from the original post.

Please give me a few days to digest the agent’s attempts before I push them to the draft branch, to keep the code reasonably readable.

2 Likes