[m-dev.] Mutually recursive tailcalls in hlc.

[Paul Bone]

On Tue, Nov 10, 2015 at 02:23:20PM +1100, Julien Fischer wrote:
> 
> Hi Paul,
> 
> On Tue, 10 Nov 2015, Paul Bone wrote:
> 
> >I feel ambivalent about it.  My main concern is that it depends on the
> >behaviour of C compilers.
> 
> It depends what you are trying to achieve.  If you want to make
> guarantees about about tailcalls being eliminated in a specified class
> of mutually recursive predicates then I think you will have to handle it
> in the Mercury compiler.  Leaving it up to the C compiler is at the very
> least sensitive to which optimization flags the C compiler is invoked
> with and the Mercury implementation itself often varies flags those in
> order to workaround bugs.  Furthermore, users have the option of setting
> C compiler optimization flags hemselves (and indeed, may have to because
> of the contents of foreign_proc pragmas.)

For YesLogic, the priority is helping to avoid stack overflows.  Some
customers give Price very large or strange documents, and unless they send
us the document that crashed Prince we usually don't know why it crashed.
Improving tail call warnings and mutually recursive tail calls will help us
ship even more reliable software.

A performance boost would also be nice, but we're not expecting anything
significant.  But I'm starting some profiling to see if this might also be
improved.  The profiling will also tell me which mutually recursive
predicates have many calls, and are going to be a priority.

> Incidentally, the trampolining technique ought to also work (with
> appropriate modifications) with both the C# and Java backends.

Agreed.  Although the relative costs of different things will be different.
I think that indirect calls may be more expensive in Java, I'd explain but
it's a bit off topic.

> >
> >Okay, so that's:
> >
> >   GCC: Yes
> >   Clang: No, XXX check the source
> >   VC++: Yes
> 
> It would be worth trying with a newer version of clang.  The version on
> my machine appears to be a little old.  (3.5 as opposed to the latest
> which is 3.8.)

It looks as if 3.8 is under development.  I was able to download and install
3.7

> I'd like to see what happens with a more realistic case than the above
> though (i.e. with C code generated by the Mercury compiler for a non toy
> program).

Okay, At -O2 GCC 5.2.1 optimized the tail calls to jumps.

Even at -O3 clang 3.7 won't optimise this.  So I guess this is GCC and MSVC
only.


-- 
Paul Bone