[SimplifyCFG/IndVarSimplify] Same-direction-subtraction strength reduction applies to tail-recursive loops but not equivalent while-loops
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Found while following up on #4729.
The same repeated-subtraction GCD algorithm gets a genuinely different,
and differently-optimized, loop shape at `-O2` on x86-64 depending on
whether it's written as a single `while` loop or as mutual tail
recursion.
`while`-form:
```c
int hcf(int a, int b)
{
while (a != 0)
{
if (a < b) b -= a;
else a -= b;
}
return b;
}
```
compiles to a single branch-free loop using `cmov`:
```asm
.LBB0_2:
cmpl %eax, %edi
movl %eax, %edx
cmovll %ecx, %edx
movl $0, %esi
cmovll %edi, %esi
subl %esi, %eax
subl %edx, %edi
jne .LBB0_2
```
Recursive form (same algorithm, tail calls):
```c
int hcf(int a, int b)
{
if (a == 0) return b;
else if (a < b) return hcf(a, b-a);
else return hcf(a-b, b);
}
```
compiles, after tail-call elimination, to a *nested* loop: a tight
2-instruction inner loop (`subl`/`jg`) that collapses a whole run of
consecutive same-direction subtractions (i.e. computing `b mod a` by
repeated subtraction) before folding the next step back into the outer
loop:
```asm
.LBB0_1: # outer loop
movl %edi, %ecx
movl %eax, %edx
.LBB0_2: # inner loop
subl %ecx, %edx
jg .LBB0_2
# bb.3
movl %edx, %edi
negl %edi
leal (%rcx,%rdx), %eax
testl %edx, %edx
jne .LBB0_1
```
Both are correct (checked against a `%`-based reference over 500,000
random inputs) and both are reasonable choices *in isolation* -- I
benchmarked them and neither dominates the other:
```
close-magnitude: loop=0.0783s rec=0.0998s (single-loop ~27% faster)
bounded-imbalance: loop=0.4252s rec=0.1907s (nested loop ~2.2x faster)
```
For inputs close in magnitude (few subtractions before the comparison
flips), the single-loop `cmov` form wins, since the nested form pays
extra fixed overhead per outer-loop transition. For inputs with a large
magnitude imbalance (many consecutive subtractions in the same
direction), the nested form wins by a wide margin, since its inner loop
costs 2 instructions per subtraction versus 8 in the `cmov` body.
The actual issue isn't that either shape is bad -- it's that LLVM only
discovers the beneficial strength reduction (collapsing a run of
same-direction recursive/loop steps into a tight inner loop) for the
tail-recursive source form, not for the `while`-loop form of the exact
same algorithm, even though tail-call elimination should leave broadly
similar loop IR behind in both cases. Ideally both forms would either
get the same treatment, or the compiler would have some way to prefer
whichever shape is better for the runtime data distribution -- though
the latter is obviously a much bigger request than the former.
Reproducer (both functions), `-O2`, `x86_64-unknown-linux-gnu`,
current trunk as of 2026-09-02.
Assisted-by: Claude Sonnet 5
Contributor guide
Research direction
Start with the two-function C reproducer in the issue and inspect the SimplifyCFG/IndVarSimplify optimization path at -O2 for x86_64. Compare the loop shapes after optimization for the while and tail-recursive forms. Done means the equivalent forms receive consistent strength reduction, with generated assembly showing the intended behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100