https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110203
Bug ID: 110203
Summary: Sum should optimize to closed form
Product: gcc
Version: 13.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: llvm at rifkin dot dev
Target Milestone: ---
For both of
int foo(int num) {
if(num == 1) return 1;
return num + foo(num - 1);
}
int bar(int num) {
int sum = 0;
for(int i = 1; i <= num; i++) {
sum += i;
}
return sum;
}
GCC emits loops:
foo(int):
xor eax, eax
cmp edi, 1
je .L8
.L2:
mov edx, edi
sub edi, 1
add eax, edx
cmp edi, 1
jne .L2
add eax, 1
ret
.L8:
mov eax, 1
ret
bar(int):
test edi, edi
jle .L12
add edi, 1
mov eax, 1
xor edx, edx
.L11:
add edx, eax
add eax, 1
cmp eax, edi
jne .L11
mov eax, edx
ret
.L12:
xor edx, edx
mov eax, edx
ret
GCC should optimize this to the closed form.
There is precedent for this transformation, llvm does it
https://godbolt.org/z/Kfffe5aPz.
