[RFC] [Arm] Fixing function size estimation?

Code Generation ARM
1

Summary

I’d like suggestions for the best way to deal with EstimateFunctionSizeInBytes in ARMFrameLowering.cpp being unreliable. Ideally, removing it completely and using a different strategy – but what?

Background

The Thumb instruction set has 16-bit branch instructions, which don’t have space to store a very large relative offset. Thumb2 introduces 32-bit branch instructions (B.W) with a longer range, but Arm v6-M (e.g. Cortex-M0) supports only Thumb1 instructions, and doesn’t have B.W. (Its successor Arm v8-M Baseline has added it.)

So, when compiling a large function for Arm v6-M, you can easily find that the available branch instructions can’t reach from one basic block to another, because they’re too far apart.

The usual solution is to use the BL instruction, which is 32 bits wide even in Thumb1, and has a longer range. BL is unconditional, so for a long-range conditional branch you must do a short-range Bcc to a BL trampoline. But also, BL has the side effect of writing a return address to the LR register, because it’s normally used as a subroutine call. In this context (using it for a branch within a function) that return address is not useful, so it must be treated simply as a corrupted register.

Therefore, in a large function, you must make sure you stack LR on function entry, so that you can still recover your return address after you use a BL within the function.

(Of course, you were doing that already if your function wanted to call any subroutine and then return. And if your function is noreturn then it doesn’t matter anyway, or at least shouldn’t. But a large leaf function might need to stack LR only because of this need to use an intra-function BL.)

This presents a phase-order problem, because ARMFrameLowering must decide whether to stack LR early in the backend, before the exact size of the generated code is known. In particular, ARMConstantIslandsPass has yet to make decisions about where to put literal pools, which can significantly affect function size.

The current solution to this is that ARMFrameLowering has a routine called EstimateFunctionSizeInBytes, which tries to guess how large the function is going to end up. If there’s a risk that it ends up big enough to need an intra-function BL, then we precautionarily stack LR.

If EstimateFunctionSizeInBytes overestimates, the cost is an unnecessary push and pop. But if it underestimates, then the effect is a compiler crash later in the backend, namely in ARMConstantIslandsPass, which is the place where BL trampolines are added if necessary.

Problem

Unfortunately, EstimateFunctionSizeInBytes (I’ll abbreviate as EFSIB from now on) has underestimated the function size, in multiple recent issues, leading to crashes in ARMConstantIslandsPass.

One of them was an easy fix: EFSIB was accidentally counting COPY as having zero size, even though each one expands into a move instruction that consumes space.

But the other one is not easy. The load instruction that reads a literal from a literal pool is also 16 bits wide, in Thumb1, so it has a similarly limited range to the branch instruction. So, in a large function reusing the same literal multiple times, ARMConstantIslandsPass may need to make more than one copy of the same literal, so that there’s a copy within reach of each load instruction that needs it. This may also involve splitting a large basic block so as to add a branch instruction skipping over a literal. But EFSIB sees only one copy of the literal, so duplicating literals is a cause of size underestimation.

For EFSIB to anticipate all of that complexity, it must either be extremely pessimistic, or essentially do most of ARMConstantIslandsPass’s work for it.

Possible answers

What can we do to avoid the risk of this kind of backend crash?

One possible approach, as I mention above, is to keep making EFSIB more and more conservative whenever we see these problems. In the duplicated-literals case, for example, we could assume that every single use of a literal requires a separate copy of the literal and a branch instruction to skip over it. This has an obvious cost (it would often stack LR in cases where it turned out to be unnecessary). Also, as mentioned in the commit that introduced EFSIB in the first place, it’s quite difficult to anticipate all the reasons a function’s size might grow during the backend. (This pessimistic approach to literal duplication is still only focusing on one possible cause of function growth.)

If EFSIB can’t be made to estimate reliably, then surely the only alternative is to get rid of it completely, and find a different approach to the whole problem. How else can you decide whether to stack LR?

From first principles, an obvious possibility is to backtrack. Wait until ARMConstantIslandsPass finds out that it has a problem (because it’s discovered that it needs to use a BL but the function hadn’t stacked LR for any other reason), and then rewind the entire backend to ARMFrameLowering and this time make it stack LR.

On the plus side, this would avoid the problem of overestimation completely. But it has obvious downsides too. It might be very difficult to do it in the LLVM pass pipeline, and if we did, I could easily imagine it setting a dangerous precedent – if there were a general mechanism for passes to request a rewind to a previous point in the pipeline to do something differently, you could easily imagine that other passes would start using it, and introduce the risk of non-convergence, as well as lots of extra compilation time.

A third possible approach would be to somehow defer the decision about stacking LR, by having ARMFrameLowering emit some kind of ambiguous MIR which can be adjusted later. That sounds complicated, because it might involve changing all the offsets in PC-relative loads as well as modifying push, pop and bx lr instructions. But maybe it’s less bad than the other two options?

LLVM Weekly - #643, April 27th 2026
[RFC][Arm] Fixing function size estimation (2)
2

How about: in the rare case where you need to emit a long branch but LR was not saved (because EFSIB was too conservative) then instead of using BL, you emit some even longer sequence like loading the target address into a register and jumping to that?

3

I thought of that, but since this happens after register allocation, you don’t have any register reliably free to use.

But I suppose you might be able to do it without corrupting any registers, with a temporary push/pop sequence along the lines of

push {r0,r1,lr}
adr r0, address_literal
ldr r1, [r0]
add r1, r1, r0
str r1, [sp, #8]
pop {r0,r1,pc}
address_literal: .word destination_address - address_literal

or perhaps a bit simpler if you know you’re in a context that doesn’t need position-independence.

4

Unless a particular constant pool is particularly large, could it be possible to chain together 2-byte branches? For example:

b .L.extra_branch
...
b .L.skip_over_extra_branch
.L.extra_branch:
b .L.destination
.L.skip_over_extra_branch:
...

This would likely mean splitting a block to place the branch, and there’s always the danger of disturbing the code-generation such that more pools are duplicated and the new branch goes out of range etc. Although I only expect us to be in this situation for functions of size that it is only slightly over the branch range so it may not happen in practice.

5

Loading a constant address is really big/slow. Chaining branches would make the pass significantly more complicated… if the function is just slightly larger than the distance limit for small branches, it’s not a big deal, but extending it to larger functions becomes hard to reason about.

I would lean towards making the estimate more conservative. And also maybe add some kind of size assertion to the backend so that we can catch cases where our size estimate is wrong even if ARMConstantIslands doesn’t actually care. It doesn’t really matter if we’re conservative: spilling LR isn’t that expensive. We just don’t want to do it for tiny leaf functions. And with a better assertion, I think we could sort out any remaining issues pretty quickly.

6

catch cases where our size estimate is wrong even if ARMConstantIslands doesn’t actually care

I wondered about that myself at one point, but I thought surely everyone would hate it, because of the breaking-in stage where the assertion was failing all the time! But maybe I should give the thought another chance.

7

I’ve had a try at the strategy suggested here, of making EFSIB much more pessimistic and also adding an unconditional check to catch underestimates. I’m not 100% sure about it, but here’s a first draft:

8

I agree with @efriedma-quic. I’ve had similar issues with the sign extension pass I’ve been developing, for code size optimizations. TTI produced many code size regressions if I trusted it too much.

To solve my code size regressions, I added a new and simple TTI function in the file X86TargetTransformInfo.cpp