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

[Paul Bone]

On Fri, Nov 06, 2015 at 12:50:12PM +1100, Zoltan Somogyi wrote:
> 
> 
> 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?

Whoops, thanks.

>  
> > 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?

No, you can generate wrappers for each of the procedures in the SCC and
leave the non-tail calls unmodified.

> 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.

Yes, I did consider that.  I'd like to do that as well as it'll be much
faster.  My proposal here is a more general solution.

Choosing when to inline raises some interesting questions.  If p calls q
multiple times but q calls p once, we should line p into q.  We might still
need to generate a normal version of p if it is called from outside the SCC.

> > 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?

I don't know yet.  It makes sense to identify the invariants using
loop_env.m.  So far I've looked at doing the general transformation as part
of HLDS->MLDS, or as an MLDS->MLDS transformation.  As HLDS->MLDS we have
the benefit of all the information in the HLDS, including trivially
(programmer effort) performing a topological sort, but as MLDS->MLDS it may
be a little simpler, not having to do the general HLDS->MLDS transformation
at the same time..

> That way, it would work for ANY backend.

Hrm..  It's not necessary at all on the low-level C backend.  And all the
other backends are MLDS backends.  I don't see the need.  However the
inlining stuff can easily (and should) be done as a HLDS->HLDS
transformation.


-- 
Paul Bone