Handling long branches
Branch instructions on most architectures use PC-relative addressingwith a limited range. When the target is too far away, the branchbecomes "out of range" and requires special handling.
Consider a large binary where main() at address 0x10000calls foo() at address 0x8010000-over 128MiB away. OnAArch64, the bl instruction can only reach ±128MiB, so thiscall cannot be encoded directly. Without proper handling, the linkerwould fail with an error like "relocation out of range." The toolchainmust handle this transparently to produce correct executables.
This article explores how compilers, assemblers, and linkers worktogether to solve the long branch problem.
- Compiler (IR to assembly): Handles branches within a function thatexceed the range of conditional branch instructions
- Assembler (assembly to relocatable file): Handles branches within asection where the distance is known at assembly time
- Linker: Handles cross-section and cross-object branches discoveredduring final layout
Branch range limitations
Different architectures have different branch range limitations.Here's a quick comparison of unconditional branch/call ranges:
| Architecture | Unconditional Branch | Conditional Branch | Notes |
|---|---|---|---|
| AArch64 | ±128MiB | ±1MiB | Range extension thunks |
| AArch32 (A32) | ±32MiB | ±32MiB | Range extension and interworking veneers |
| AArch32 (T32) | ±16MiB | ±1MiB | Thumb has shorter ranges |
| PowerPC64 | ±32MiB | ±32KiB | Range extension and TOC/NOTOC interworking thunks |
| RISC-V | ±1MiB (jal) |
±4KiB | Linker relaxation |
| x86-64 | ±2GiB | ±2GiB | Code models or thunk extension |
The following subsections provide detailed per-architectureinformation, including relocation types relevant for linkerimplementation.
AArch32
In A32 state:
- Branch (
b/b<cond>), conditionalbranch and link (bl<cond>)(R_ARM_JUMP24): ±32MiB - Unconditional branch and link (
bl/blx,R_ARM_CALL): ±32MiB
Note: R_ARM_CALL is for unconditionalbl/blx which can be relaxed to BLX inline;R_ARM_JUMP24 is for branches which require a veneer forinterworking.
In T32 state:
- Conditional branch (
b<cond>,R_ARM_THM_JUMP8): ±256 bytes - Short unconditional branch (
b,R_ARM_THM_JUMP11): ±2KiB - ARMv5T branch and link (
bl/blx,R_ARM_THM_CALL): ±4MiB - ARMv6T2 wide conditional branch (
b<cond>.w,R_ARM_THM_JUMP19): ±1MiB - ARMv6T2 wide branch (
b.w,R_ARM_THM_JUMP24): ±16MiB - ARMv6T2 wide branch and link (
bl/blx,R_ARM_THM_CALL): ±16MiB.R_ARM_THM_CALLcan berelaxed to BLX.
AArch64
- Test and compare branches(
tbnz/tbz/cbnz/cbz):±32KiB - Conditional branches (
b.<cond>): ±1MiB - Unconditional branches (
b/bl):±128MiB
PowerPC
- Conditional branch (
bc/bcl,R_PPC64_REL14): ±32KiB - Unconditional branch (
b/bl,R_PPC64_REL24/R_PPC64_REL24_NOTOC):±32MiB
RISC-V
- Compressed
c.beqz: ±256 bytes - Compressed
c.jal: ±2KiB -
jalr(I-type immediate): ±2KiB - Conditional branches(
beq/bne/blt/bge/bltu/bgeu,B-type immediate): ±4KiB -
jal(J-type immediate,PseudoBR):±1MiB -
PseudoJump(usingauipc+jalr): ±2GiB
Qualcomm uC Branch Immediate extension (Xqcibi):
-
qc.beqi/qc.bnei/qc.blti/qc.bgei/qc.bltui/qc.bgeui(32-bit, 5-bit compare immediate): ±4KiB -
qc.e.beqi/qc.e.bnei/qc.e.blti/qc.e.bgei/qc.e.bltui/qc.e.bgeui(48-bit, 16-bit compare immediate): ±4KiB
Qualcomm uC Long Branch extension (Xqcilb):
-
qc.e.j/qc.e.jal(48-bit,R_RISCV_VENDOR(QUALCOMM)+R_RISCV_QC_E_CALL_PLT): ±2GiB
SPARC
- Compare and branch (
cxbe,R_SPARC_5): ±64bytes - Conditional branches (
bcc,R_SPARC_WDISP19): ±1MiB -
call(R_SPARC_WDISP30): ±2GiB
Note: lld does not implement range extension thunks for SPARC.
x86-64
- Short conditional jump (
Jcc rel8): -128 to +127bytes - Short unconditional jump (
JMP rel8): -128 to +127bytes - Near conditional jump (
Jcc rel32): ±2GiB - Near unconditional jump (
JMP rel32): ±2GiB
With a ±2GiB range for near jumps, x86-64 rarely encountersout-of-range branches in practice. A single text section would need toexceed 2GiB before thunks become necessary. For this reason, mostlinkers (including lld) do not implement range extension thunks forx86-64.
Compiler: branch relaxation
The compiler typically generates branches using a form with a largerange. However, certain conditional branches may still go out of rangewithin a function.
The compiler measures branch distances and relaxes out-of-rangebranches. In LLVM, this is handled by the BranchRelaxationpass, which runs just before AsmPrinter.
Different backends have their own implementations:
-
BranchRelaxation: AArch64, AMDGPU, AVR, RISC-V -
HexagonBranchRelaxation: Hexagon -
PPCBranchSelector: PowerPC -
SystemZLongBranch: SystemZ -
MipsBranchExpansion: MIPS -
MSP430BSel: MSP430
For a conditional branch that is out of range, the pass typicallyinverts the condition and inserts an unconditional branch:
1 |
# Before relaxation (out of range) |
Assembler: instructionrelaxation
The assembler converts assembly to machine code. When the target of abranch is within the same section and the distance is known at assemblytime, the assembler can select the appropriate encoding. This isdistinct from linker thunks, which handle cross-section or cross-objectreferences where distances aren't known until link time.
Assembler instruction relaxation handles two cases (see
-
Span-dependent instructions: Select a largerencoding when the displacement exceeds the range of the smallerencoding. For x86, a short jump (
jmp rel8) can be relaxedto a near jump (jmp rel32). -
Conditional branch transform: Invert the conditionand insert an unconditional branch. On RISC-V, a
bltmightbe relaxed tobgeplus an unconditional branch.
The assembler uses an iterative layout algorithm that alternatesbetween fragment offset assignment and relaxation until all fragmentsbecome legalized. See
Linker: range extensionthunks
When the linker resolves relocations, it may discover that a branchtarget is out of range. At this point, the instruction encoding isfixed, so the linker cannot simply change the instruction. Instead, itgenerates range extension thunks (also called veneers,branch stubs, or trampolines).
A thunk is a small piece of linker-generated code that can reach theactual target using a longer sequence of instructions. The originalbranch is redirected to the thunk, which then jumps to the realdestination.
Range extension thunks are one type of linker-generated thunk. Othertypes include:
-
ARM interworking veneers: Switch between ARM andThumb instruction sets (see
Linker notes onAArch32) -
MIPS LA25 thunks: Enable PIC and non-PIC codeinteroperability (see
Toolchain notes onMIPS) -
PowerPC64 TOC/NOTOC thunks: Handle calls betweenfunctions using different TOC pointer conventions (see
Linker notes on PowerISA)
Short range vs long rangethunks
A short range thunk (see
Long range thunks use indirection and can jump to (practically)arbitrary locations.
1 |
// Short range thunk: single branch, 4 bytes |
Thunk examples
AArch32 (PIC) (see
1
2
3
4
5__ARMV7PILongThunk_dst:
movw ip, :lower16:(dst - .) ; ip = intra-procedure-call scratch register
movt ip, :upper16:(dst - .)
add ip, ip, pc
bx ip
PowerPC64 ELFv2 (see
1
2
3
4
5__long_branch_dst:
addis 12, 2, .branch_lt@ha # Load high bits from branch lookup table
ld 12, .branch_lt@l(12) # Load target address
mtctr 12 # Move to count register
bctr # Branch to count register
Thunk impact ondebugging and profiling
Thunks are transparent at the source level but visible in low-leveltools:
-
Stack traces: May show thunk symbols (e.g.,
__AArch64ADRPThunk_foo) between caller and callee - Profilers: Samples may attribute time to thunkcode; some profilers aggregate thunk time with the target function
-
Disassembly:
objdumporllvm-objdumpwill show thunk sections interspersed withregular code - Code size: Each thunk adds bytes; large binariesmay have thousands of thunks
lld/ELF's thunk creationalgorithm
lld/ELF uses a multi-pass algorithm infinalizeAddressDependentContent:
1 |
assignAddresses(); |
Key details:
- Multi-pass: Iterates until convergence (max 30passes). Adding thunks changes addresses, potentially puttingpreviously-in-range calls out of range.
-
Pre-allocated ThunkSections: On pass 0,
createInitialThunkSectionsplaces emptyThunkSections at regular intervals(thunkSectionSpacing). For AArch64: 128 MiB - 0x30000 ≈127.8 MiB. -
Thunk reuse:
getThunkreturns existingthunk if one exists for the same target;normalizeExistingThunkchecks if a previously-created thunkis still in range. -
ThunkSection placement:
getISDThunkSecfinds a ThunkSection within branch range of the call site, or createsone adjacent to the calling InputSection.
lld/MachO's thunk creationalgorithm
lld/MachO uses a single-pass algorithm inTextOutputSection::finalize:
1 |
for (callIdx = 0; callIdx < inputs.size(); ++callIdx) { |
Key differences from lld/ELF:
- Single pass: Addresses are assigned monotonicallyand never revisited
-
Slop reservation: Reserves
slopScale * thunkSizebytes (default: 256 × 12 = 3072 byteson ARM64) to leave room for future thunks -
Thunk naming:
<function>.thunk.<sequence>where sequenceincrements per target
Thunkstarvation problem: If many consecutive branches need thunks, eachthunk (12 bytes) consumes slop faster than call sites (4 bytes apart)advance. The test lld/test/MachO/arm64-thunk-starvation.sdemonstrates this edge case. Mitigation is increasing--slop-scale, but pathological cases with hundreds ofconsecutive out-of-range callees can still fail.
mold's thunk creationalgorithm
mold uses a two-pass approach: first pessimistically over-allocatethunks, then remove unnecessary ones.
Intuition: It's safe to allocate thunk space andlater shrink it, but unsafe to add thunks after addresses are assigned(would create gaps breaking existing references).
Pass 1 (create_range_extension_thunks):Process sections in batches using a sliding window. The window tracksfour positions:
1 |
Sections: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] ... |
- [B, C) = current batch of sections to process (size≤ branch_distance/5)
- A = earliest section still reachable from C (forthunk expiration)
- D = where to place the thunk (furthest pointreachable from B)
1 |
// Simplified from OutputSection<E>::create_range_extension_thunks |
Pass 2 (remove_redundant_thunks): Afterfinal addresses are known, remove thunk entries for symbols actually inrange.
Key characteristics:
- Pessimistic over-allocation: Assumes allout-of-section calls need thunks; safe to shrink later
- Batch size: branch_distance/5 (25.6 MiB forAArch64, 3.2 MiB for AArch32)
- Parallelism: Uses TBB for parallel relocationscanning within each batch
-
Single branch range: Uses one conservative
branch_distanceper architecture. For AArch32, uses ±16 MiB(Thumb limit) for all branches, whereas lld/ELF uses ±32 MiB for A32branches. - Thunk size not accounted in D-advancement: Theactual thunk group size is unknown when advancing D, so the end of alarge thunk group may be unreachable from the beginning of thebatch.
- No convergence loop: Single forward pass foraddress assignment, no risk of non-convergence
Comparing thunk algorithms
| Aspect | lld/ELF | lld/MachO | mold |
|---|---|---|---|
| Passes | Multi-pass (max 30) | Single-pass | Two-pass |
| Strategy | Iterative refinement | Greedy | Greedy |
| Thunk placement | Pre-allocated at intervals | Inline with slop reservation | Batch-based at intervals |
| Convergence | Always (bounded iterations) | Almost always | Almost always |
| Range handling | Per-relocation type | Single conservative range | Single conservative range |
| Parallelism | Sequential | Sequential | Parallel (TBB) |
Linker relaxation (RISC-V)
RISC-V takes a different approach: instead of only expandingbranches, it can also shrink instruction sequences whenthe target is close enough.
Consider a function call using the callpseudo-instruction, which expands to auipc +jalr:
1
2
3
4
5# Before linking (8 bytes)
call ext
# Expands to:
# auipc ra, %pcrel_hi(ext)
# jalr ra, ra, %pcrel_lo(ext)
If ext is within ±1MiB, the linker can relax this to:
1
2# After relaxation (4 bytes)
jal ext
This is enabled by R_RISCV_RELAX relocations thataccompany R_RISCV_CALL relocations. TheR_RISCV_RELAX relocation signals to the linker that thisinstruction sequence is a candidate for shrinking.
Example object code before linking:
1
2
3
4
5
6
7
8
90000000000000006 <foo>:
6: 97 00 00 00 auipc ra, 0
R_RISCV_CALL ext
R_RISCV_RELAX *ABS*
a: e7 80 00 00 jalr ra
e: 97 00 00 00 auipc ra, 0
R_RISCV_CALL ext
R_RISCV_RELAX *ABS*
12: e7 80 00 00 jalr ra
After linking with relaxation enabled, the 8-byteauipc+jalr pairs become 4-bytejal instructions:
1
2
3
4
5
60000000000000244 <foo>:
244: 41 11 addi sp, sp, -16
246: 06 e4 sd ra, 8(sp)
248: ef 00 80 01 jal ext
24c: ef 00 40 01 jal ext
250: ef 00 00 01 jal ext
When the linker deletes instructions, it must also adjust:
- Subsequent instruction offsets within the section
- Symbol addresses
- Other relocations that reference affected locations
- Alignment directives (
R_RISCV_ALIGN)
This makes RISC-V linker relaxation more complex than thunkinsertion, but it provides code size benefits that other architecturescannot achieve at link time.
Diagnosing out-of-rangeerrors
When you encounter a "relocation out of range" error, here are somediagnostic steps:
Check the error message: lld reports the sourcelocation, relocation type, and the distance. For example:
1
ld.lld: error: a.o:(.text+0x1000): relocation R_AARCH64_CALL26 out of range: 150000000 is not in [-134217728, 134217727]
Use
--verboseor-Map: Generate a link map to see sectionlayout and identify which sections are far apart.Consider
-ffunction-sections:Splitting functions into separate sections gives the linker moreflexibility in placement, potentially reducing distances.Check for large data in
.text:Embedded data (jump tables, constant pools) can push functions apart.Some compilers have options to place these elsewhere.LTO considerations: Link-time optimization candramatically change code layout. If thunk-related issues appear onlywith LTO, the optimizer may be creating larger functions or differentinlining decisions.
Summary
Handling long branches requires coordination across thetoolchain:
| Stage | Technique | Example |
|---|---|---|
| Compiler | Branch relaxation pass | Invert condition + add unconditional jump |
| Assembler | Instruction relaxation | Short jump to near jump |
| Linker | Range extension thunks | Generate trampolines |
| Linker | Linker relaxation | Shrink auipc+jalr to jal(RISC-V) |
The linker's thunk generation is particularly important for largeprograms where cross-compilation-unit calls may exceed branch ranges.Different linkers use different algorithms with various tradeoffsbetween complexity, optimality, and robustness.
RISC-V's linker relaxation is unique in that it can both expand andshrink code, optimizing for both correctness and code size.

