On 04/01/2010, at 3:01 PM, Jon Harrop wrote:> On Monday 04 January 2010 01:12:55 Simon Harris wrote: >> I'm investigating "improving" the TCO facilities in LLVM to provide for >> "hard" tail calls. Specifically, this would involve extending the existing >> implementation to discard the stack frame for the caller before executing >> the callee. I would then like to extend this further by performing hard >> tail calls on _all_ returning calls that no longer require the stack frame. >> >> A colleague of mine and I have looked into it and prima facie believe that >> it's entirely feasible. I wanted to ask the list if there was any interest, >> any objections, and of course, anything pointers/tips that may prove >> useful. > > I am certainly interested in tail calls because my HLVM project relies upon > LLVM's tail call elimination. However, I do not understand what tail calls > LLVM is not currently eliminating that you plan to eliminate?Mutual recursion for a start: def a(n) n <= 0 ? "DONE" : b(n - 1) end def b(n) n <= 0 ? "DONE" : a(n - 1) end a(10000000) Boom! -- Simon Harris w: http://www.harukizaemon.com/ e: haruki.zaemon at gmail.com m: +61 417 505 611 t: @haruki_zaemon
On 04/01/2010, at 3:50 PM, Jon Harrop wrote:> On Monday 04 January 2010 03:33:06 Simon Harris wrote: >> On 04/01/2010, at 3:01 PM, Jon Harrop wrote: >>> I am certainly interested in tail calls because my HLVM project relies >>> upon LLVM's tail call elimination. However, I do not understand what tail >>> calls LLVM is not currently eliminating that you plan to eliminate? >> >> Mutual recursion for a start: >> >> def a(n) >> n <= 0 ? "DONE" : b(n - 1) >> end >> >> def b(n) >> n <= 0 ? "DONE" : a(n - 1) >> end >> >> a(10000000) >> >> Boom! > > LLVM's TCO already handles mutual recursion.Hmm... OK. Perhaps it's the way it's being used by MacRuby and Rubinius. Drat! Back to the drawing board :(
On Monday 04 January 2010 03:33:06 Simon Harris wrote:> On 04/01/2010, at 3:01 PM, Jon Harrop wrote: > > I am certainly interested in tail calls because my HLVM project relies > > upon LLVM's tail call elimination. However, I do not understand what tail > > calls LLVM is not currently eliminating that you plan to eliminate? > > Mutual recursion for a start: > > def a(n) > n <= 0 ? "DONE" : b(n - 1) > end > > def b(n) > n <= 0 ? "DONE" : a(n - 1) > end > > a(10000000) > > Boom!LLVM's TCO already handles mutual recursion. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e
On Sun, Jan 3, 2010 at 10:50 PM, Jon Harrop <jon at ffconsultancy.com> wrote:> On Monday 04 January 2010 03:33:06 Simon Harris wrote: >> On 04/01/2010, at 3:01 PM, Jon Harrop wrote: >> > I am certainly interested in tail calls because my HLVM project relies >> > upon LLVM's tail call elimination. However, I do not understand what tail >> > calls LLVM is not currently eliminating that you plan to eliminate? >> >> Mutual recursion for a start: >> >> def a(n) >> n <= 0 ? "DONE" : b(n - 1) >> end >> >> def b(n) >> n <= 0 ? "DONE" : a(n - 1) >> end >> >> a(10000000) >> >> Boom! > > LLVM's TCO already handles mutual recursion.Only for fastcc functions compiled with -tailcallopt, right? http://llvm.org/docs/CodeGenerator.html#tailcallopt I believe gcc manages to support tail calls in many more cases, and this restriction in llvm confuses lots of newcomers. It would be very worthwhile if someone wanted to remove it.