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

[Zoltan Somogyi]

On Fri, 6 Nov 2015 11:37:19 +1100, Paul Bone <paul at bone.id.au> wrote:
> I propose to handle mutually recursive tailcalls using a trampoline.
> Without --no-optimize-tailcalls the generated C code for the inner loop of
> mandelbrot looks like this:
> 
> static void MR_CALL 
> mandelbrot__escape_7_p_0(
>   MR_Float mandelbrot__Nr_8,
>   MR_Float mandelbrot__Ni_9,
>   MR_Float mandelbrot__Cr_10,
>   MR_Float mandelbrot__Ci_11,
>   MR_Integer mandelbrot__MaxIters_12,
>   MR_Integer mandelbrot__STATE_VARIABLE_Iters_0_18,
>   MR_Integer * mandelbrot__STATE_VARIABLE_Iters_19)
> {
>   {
>     MR_bool mandelbrot__succeeded;
>     MR_Integer mandelbrot__V_20_20 = (MR_Integer) 0;
> 
>     ...;
>     
>     if (...)
>       ...;
> 
>       mandelbrot__escape_7_p_0(mandelbrot__Rr_16, mandelbrot__Ri_17, mandelbrot__Cr_10, mandelbrot__Ci_11, mandelbrot__V_36_36, mandelbrot__STATE_VARIABLE_Iters_34_34, mandelbrot__STATE_VARIABLE_Iters_19);
>     else {
>       ...;
>       *mandelbrot__STATE_VARIABLE_Iters_19 = (MR_Integer) -1;
>     }
>   }
> }

Why would the code look like that *without* --no-optimize-tailcalls?
Don't you mean *with* --no-optimize-tailcalls, i.e. without the optimization
of tailcalls?
 
> I've transformed it to this:

Am I correct in thinking that this scheme will work only if no procedure
in the clique makes any recursive calls that aren't tail calls?

And have you considered simply inlining recursive calls?
If a clique has only two procedures, say p and q, and
if p only calls q and q only calls p, then inlining each procedure
in the other will work. This arrangement is likely to be both simpler
to implement and to yield faster code than your trampoline.
Of course, I don't know if your motivating example fits
these restrictions.

> The reason I think this is a suitable proxy for mutual recursion is that it
> uses almost the same transformation.

OK, I get the idea. You don't have to send me any scripts.

> There are a number of potential optimisations that could be made.  For
> example loop invariants do not need to be re-saved into the structure, they
> would need to form a structure such as.

Wouldn't you want to implement that as an extension of the existing loop_inv.m?
That way, it would work for ANY backend.

Zoltan.