[m-dev.] Mutually recursive tailcalls in hlc.
Paul Bone
paul at bone.id.au
Fri Nov 6 15:07:37 AEDT 2015
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
More information about the developers
mailing list