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

[Peter Wang]

On Mon, 9 Nov 2015 12:58:32 +1100, Paul Bone <paul at bone.id.au> wrote:
> On Sat, Nov 07, 2015 at 01:49:37PM +1100, Mark Brown wrote:
> > On Sat, Nov 7, 2015 at 1:25 PM, Zoltan Somogyi
> > <zoltan.somogyi at runbox.com> wrote:
> > > On Sat, 7 Nov 2015 06:06:21 +1100, Mark Brown <mark at mercurylang.org> wrote:
> > >> 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?
> > >
> > > Two functions with the same number of arguments may still have
> > > different stack frame sizes,
> > 
> > Yes, I know. I think Paul may be mistaken about gcc's criteria,
> > however: "the compiler considers two functions as being siblings if
> > they share the same structural equivalence of return types, as well as
> > matching space requirements of their arguments" [1]. That should be
> > easier to satisfy than having the same stack size (I haven't tried it
> > though).
> 
> I wasn't sure, But I was surprised to hear that C compilers do this at all.
> My reference to "the same frame size" is based on a comment that Peter W.
> made in a YesLogic meeting.  I didn't seek further information though.

I don't remember making that comment about exact frame sizes (or any
such discussion, actually).  It sounds unnecessarily restrictive a
condition and hard to satisfy.

> > [1] http://www.drdobbs.com/tackling-c-tail-calls/184401756
> 
> Interesting.
> 
> This article seems to think that Zoltan and Fergus invented the trampoline.
> I'm pretty sure it was invented long before.
> 
> More practically.  The article explains why C compilers don't generally
> optimize mutual recursion.  What I don't understand is if all the code is
> static, and in the same C file, then why can't the compiler do inlining or
> avoid the restrictions of the ABI completely to gain tail recursion?  I
> suspect that the answer is because it's not important enough to try.

Note that article is from 2004.

Regardless, I think we should have the trampoline transformation (or
something similar) available as we cannot depend on tail call
elimination as it is not guaranteed by any C standard anyway.

Peter