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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Bruce Hoult via llvm-dev
   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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

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

Bruce Hoult via llvm-dev
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 <[hidden email]> 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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev