search

Quuxplusone / LLVMBugzillaTest

0 stars 0 forks source link

Missed accumulator recursion elimination #50428

Open Quuxplusone opened 3 years ago

Quuxplusone commented 3 years ago
Bugzilla Link PR51461
Status NEW
Importance P enhancement
Reported by Jeremy R. (llvm@rifkin.dev)
Reported on 2021-08-12 13:49:13 -0700
Last modified on 2021-08-13 03:09:13 -0700
Version trunk
Hardware PC Windows NT
CC craig.topper@gmail.com, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also 
Of the following simple recursive functions, LLVM is able to eliminate
recursion for foo but not bar:

int foo(int n) {
    if(n <= 0) return 1;
    return 2 + foo(n - 1);
}
int bar(int n) {
    if(n <= 0) return 1;
    return 2 * bar(n - 1);
}

GCC optimizes both. https://godbolt.org/z/rozMcn6o4.
Quuxplusone commented 3 years ago

Seems to be because the multiply by 2 in bar was turned into a shift by 1. If you change it to a 3, it works.

Quuxplusone commented 3 years ago

We can probably fix this by turning the shift back into a multiply if it would allow us to remove the recursion. The Reassociate pass does something similar.