llvm / llvm/llvm-project

Missed optimization with a loop that multiplies counter by 2 until overflow

Open
#168,580 0 comments 0 reactions 0 assignees View on GitHub
loopoptim missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Test code

```c
#include
#include
#include

extern void subroutine(size_t x);

void func1a(void) {
size_t x = 1;
while (true) {
subroutine(x);
if (x > SIZE_MAX / 2)
break;
x *= 2;
}
}

void func1b(void) {
size_t x = 1;
while (true) {
subroutine(x);
if (__builtin_add_overflow(x, x, &x))
break;
}
}

void func1c(void) {
size_t x = 1;
while (true) {
subroutine(x);
if (__builtin_mul_overflow(x, (size_t)2, &x))
break;
}
}
```

x86-64 Clang 21.1.0 with `-Os` option produces:

```assembly
func1a:
pushq %rbx
movl $1, %ebx
.LBB2_1:
movq %rbx, %rdi
callq subroutine@PLT
testq %rbx, %rbx
leaq (%rbx,%rbx), %rbx
jns .LBB2_1
popq %rbx
retq

func1b:
pushq %rbx
movl $1, %ebx
.LBB3_1:
movq %rbx, %rdi
callq subroutine@PLT
addq %rbx, %rbx
jae .LBB3_1
popq %rbx
retq
```

(`func1c` assembly omitted because it's the same as `func1a`)
([Compiler Explorer link](https://godbolt.org/z/Y5dsPnehd))

While the conditional `(x > SIZE_MAX / 2)` can be converted into a "test if sign bit is set" check, it can miss that `x` would multiply by 2 afterward, so the code can be smaller by checking the carry bit after addition.

The expected result is `func1a` and `func1c` both optimize to `func1b`.

Note that I have also tested with AArch64 Clang and it has the similar problem.

EDIT: [I also reported in GCC](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=122791)

Contributor guide

Open the contributing guide

Research direction

Start by compiling the supplied C reproducer with the x86-64 and AArch64 configurations described, and inspect the Compiler Explorer link for the generated assembly. Trace the optimization responsible for the differing func1a/func1c and func1b output; done means both equivalent function pairs produce the smaller carry-checking form.

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
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.