llvm / llvm/llvm-project

excessive code size for function ending in sequence of tail calls

Open
#186,530 3 comments 0 reactions 0 assignees View on GitHub
llvm:codesize missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

For:

```llvm
define void @_CF.Main(ptr nonnull %v, ptr %cv, ptr %r, ptr %cr) local_unnamed_addr #2 !dbg !16 {
entry:
%call.i1 = tail call noundef nonnull align 4 dereferenceable(4) ptr @_ZNKOSt2_C8optionalIiE5valueEv(ptr noundef nonnull align 4 dereferenceable(5) %v) #2, !dbg !25
%call.i = tail call noundef nonnull align 4 dereferenceable(4) ptr @_ZNKOSt2_C8optionalIiE5valueEv(ptr noundef nonnull align 4 dereferenceable(5) %cv) #2, !dbg !26
%optional.value.call = tail call ptr @_ZNRSt2_C8optionalIiE5valueEv(ptr %r) #2, !dbg !27
%call.i2 = tail call noundef nonnull align 4 dereferenceable(4) ptr @_ZNKRSt2_C8optionalIiE5valueEv(ptr noundef nonnull align 4 dereferenceable(5) %cr) #2, !dbg !28
ret void, !dbg !29
}
```

LLVM generates (when optimizing for speed or code size):

```assembly
pushq %r15
pushq %r14
pushq %rbx
movq %rcx, %rbx
movq %rdx, %r14
movq %rsi, %r15
callq _ZNKOSt2_C8optionalIiE5valueEv
movq %r15, %rdi
callq _ZNKOSt2_C8optionalIiE5valueEv
movq %r14, %rdi
callq _ZNRSt2_C8optionalIiE5valueEv
movq %rbx, %rdi
popq %rbx
popq %r14
popq %r15
jmp _ZNKRSt2_C8optionalIiE5valueEv
```

I can see why that happens, but it seems like a missed opportunity for a peephole optimization. It seems to me that we ought to be able to reduce this to:

```assembly
pushq %rcx
pushq %rdx
pushq %rsi
callq _ZNKOSt2_C8optionalIiE5valueEv
popq %rdi
callq _ZNKOSt2_C8optionalIiE5valueEv
popq %rdi
callq _ZNRSt2_C8optionalIiE5valueEv
popq %rdi
jmp _ZNKRSt2_C8optionalIiE5valueEv
```

The logic here is: `%rbx` is spilled only so that we can use it to save a value that we use immediately before the epilogue. Therefore we can instead push the value that we would have saved into `%rbx`, and pop it directly into the register we want to use it from:

```assembly
pushd %reg
movq something, %reg
; don't use other
movq %reg, %callee-saved-reg
popd %reg
; rest of epilogue
; use of %callee-saved-reg
```
->
```assembly
pushd something
; don't use other
; rest of epilogue
popd %callee-saved-reg
; use of %callee-saved-reg
```

Iterating between that peephole and sinking a tail call past the epilogue seems like it'd perform this transformation.

Contributor guide

Open the contributing guide

Research direction

The issue names no source files or tests. Start by tracing the LLVM x86 code-generation path that produces the shown prologue, calls, and epilogue, then inspect existing peephole and tail-call handling; done means the redundant callee-saved register saves are avoided while preserving the tail-call sequence.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.