Missed optimization with a loop that multiplies counter by 2 until overflow
- 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
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