[llvm-dev] Why doesn't tail recursion elimination work?

Bruce Hoult via llvm-dev llvm-dev at lists.llvm.org
Sat Jun 2 02:03:52 PDT 2018


Interesting.

gcc does tail recursion elimination on it.

Clang does if you rewrite it like this:

int A[10000];

int MulRedRec(int N) {
    if (N < 0)
        return 1;
    return  A[N] * MulRedRec(N - 1);
}

That's more or less what gcc does by itself.

On Sat, Jun 2, 2018 at 8:32 PM, Alex Susu via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

>   Hello.
>     Could you please tell me why is not LLVM performing tail recursion
> elimination on the following function:
>       int A[10000];
>
>       int MulRedRec(int N) {
>           if (N == 0)
>               return A[0];
>           return A[N] * MulRedRec(N - 1);
>       }
>
>     I ask also because, for example, for the following function LLVM is
> able to eliminate tail recursion:
>       int FactRec(int N) {
>           if (N == 0)
>               return 1;
>           return N * FactRec(N - 1);
>       }
>
>     Looking on the debug information printed by opt I was able to find
> some differences in behavior when opt runs on each of the functions above -
> I can detail more on these differences.
>
>   Thank you very much,
>     Alex
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180602/392c112f/attachment.html>


More information about the llvm-dev mailing list