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

Mark Brown mark at mercurylang.org
Tue Nov 10 00:39:30 AEDT 2015

On Mon, Nov 9, 2015 at 12:27 PM, Paul Bone <paul at bone.id.au> wrote:
> On Sat, Nov 07, 2015 at 06:06:21AM +1100, Mark Brown wrote:
>> On Fri, Nov 6, 2015 at 11:37 AM, Paul Bone <paul at bone.id.au> wrote:
>> > I've transformed it to this:
>> >
>> > /* Struct is used to represent arguments for recursive calls */
>> > typedef struct {
>> >   MR_Float Nr;
>> >   MR_Float Ni;
>> >   MR_Float Cr;
>> >   MR_Float Ci;
>> >   MR_Integer MaxIters;
>> >   MR_Integer Iters_0;
>> >   MR_Integer * Iters;
>> > } escape_data;
>> If all the functions in the SCC take something like this as an
>> argument, and return void, would gcc already make the calls tail
>> recursive? Come to think of it, could you meet gcc's criteria by just
>> padding out the functions in the SCC so they all have the same number
>> of arguments?
> Zoltan has already said that this is only one factor in the stack frame
> sizes.  In addition to this I want to avoid depending on depending on any
> behaviour of a C compiler in the high level C backend.  That's what the
> low-level C backend is for. :-P

Zoltan is correct. And you have not answered my questions!

> That said if we thought that a majority of popular C compilers could
> optimise mutual recursion in the general case, then I wouldn't bother making
> this change to Mercury.  I'm pretty sure that that's not the case.

I was asking about a conditional case, not the general case. You're
right that I should ask about more than just gcc, though.

Let me try again with a specific condition. Can the compilers we want
perform tail call elimination if the signatures of the caller and
callee are the same? Your argument transformation satisfies this
condition, and the optimizations you mentioned are also relevant, but
the actual trampoline would be redundant and may impede other C
optimizations (such as inlining).

Like I said earlier, it's not that I disagree with your proposal. But
if someone asks, I'd like to be able to name a compiler we rely on
that doesn't do tail call elimination under this condition.


More information about the developers mailing list