search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.31k stars 11.69k forks source link

Missed accumulator recursion elimination #50803

Open 470e7f89-017b-4dca-8bb4-aa88c7fd5a01 opened 3 years ago

470e7f89-017b-4dca-8bb4-aa88c7fd5a01 commented 3 years ago
Bugzilla Link 51461
Version trunk
OS Windows NT
CC @topperc,@RKSimon

Extended Description

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.

topperc 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.

topperc 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.