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

[Paul Bone]

The high level backends do not support optimising mutual recursion.  But if
they did fewer programs would have stack overflows and some programs may run
faster.

I setup a small test to see if it was worthwhile investigating further (and
it is!).  I've compiled mandelbrot in hlc.gc with --no-optimise-tailcalls
--no-c-optimize.  The C optimisations are disabled because C may be
optimising tailcalls for me.  Then edited the generated C code to create my
test.  This example uses direct recursion, that's okay, I'm using it as a
proxy for mutual recursion because with this small benchmark I can
confidently modify the hand generated C files to setup my test.

I have three sinarios:

    Normal: compiled without --no-optimiise-tailcalls.  This represents the
            performance if somehow C supported native mutual recursion.

    No tailcalls: Compiled with --no-tailcalls, this represents the current
                  performance for mutually-recursive code.

    Trampoline: My test, a trampoline transformation.

My aim was that the trampoline code is no slower than the no-tailcalls code.
That way getting constant stack space usage for mutually recursive code does
not come at a performance cost.

    ./mandelbrot-normal -x 800 -y 800 -d -p no  29.12s user 0.01s system 99% cpu 29.153 total

    ./mandelbrot-no-tailcalls -x 800 -y 800 -d -p no  40.04s user 0.00s system 99% cpu 40.082 total

    ./mandelbrot-Trampoline -x 800 -y 800 -d -p no  35.36s user 0.00s system 99% cpu 35.401 total

The trampoline transformation creates code that is faster than the
no-tailcalls case, which is the best I could have hoped for.  This test case
is a micro-benchmark and so the effect is exaggerated.  Nevertheless using a
transformation like this will allow mutually recursive code to run on
constant stack space, and perhaps improve performance at the same time.

I propose to introduce such a transformation for mutually recursive code
within the same module.  That is, only on SCCs with more than two
procedures.


-- 
Paul Bone