"Paul A. Clayton" <paaronclayton@gmail.com> writes:
>I also vaguely recall reading at some point that even
>recursion that was "easy" to convert to tail recursion was
>not handled by gcc (also many years ago).

What looks like a tail-call to a Lisp or Scheme programmer actually is
not when it comes to C. That's because in C calling conventions, the
caller is responsible for cleaning up the stack, and this aspect of
the calling conventions is necessitated by the combination of varargs
and the optionality of function declarations.

So when in a C program you have

...
return foo(...);
}

in assembly language this is:

call foo
add $96, %rsp ;or something like that
return

and tail-call elimination of that is not possible in general. gcc has
something called sib-call elimination ("sib" for sibling), and AFAIK
this includes tail-recursion elimination, but I expect that even that
does not work at all times, e.g., because a pointer is passed to the
called function, and the C compiler cannot prove that it does not
point to something that is on the stack frame of the caller.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 1/8/2024 8:25 AM, Paul A. Clayton wrote:
> On 1/2/24 2:10 PM, MitchAlsup wrote:
>> Thomas Koenig wrote:
>>
>>> Compilers often do not do a good job of replacing recursion
>>> with iteration (is there a verb for that? Maybe it can be called
>>> iterationizing?), so it is something to consider if an algorithm
>>> is at all time critical or stack space is problematic.
>>
>>
>> Tail recursion elimination.
>
> I thought compilers generally were good at tail recursion
> elimination but did not attempt "flattening" something like
> flood-fill (which is not "tail recursion" but could avoid
> some of the function call overhead). (I.e., I vaguely
> remember over a decade ago noticing that this case was not
> optimized — for the samegnome game which has a small board
> so recursive depth and call overhead was not really significant.)
>
> I also vaguely recall reading at some point that even
> recursion that was "easy" to convert to tail recursion was
> not handled by gcc (also many years ago).

AFAIK:
Tail-call optimization is not really a thing in general in C;
But, at the same time, for the most part people are not writing
tail-recursive code in C, with the rare exception of a function whose
sole purpose is to wrap a call to another function, which could
in-premise be optimized into potentially a few register moves and
similar followed by a branch.

Granted, I guess trying to optimize the "function which just calls
another function" case could be something worth looking into whether it
would make sense to try to add an optimization case for it.

Anton Ertl wrote:

> "Paul A. Clayton" <paaronclayton@gmail.com> writes:
>>I also vaguely recall reading at some point that even
>>recursion that was "easy" to convert to tail recursion was
>>not handled by gcc (also many years ago).

> What looks like a tail-call to a Lisp or Scheme programmer actually is
> not when it comes to C. That's because in C calling conventions, the
> caller is responsible for cleaning up the stack, and this aspect of
> the calling conventions is necessitated by the combination of varargs
> and the optionality of function declarations.

Both the caller and the callee are responsible for cleaning up their own
parts of the stack including argument passing and result returning.

My 66000 ABU is varargs compliant and yet the caller does not need to
know the function it is calling is varargs. Caller just lobs up to 8
arguments into R1..R8 with argument[9]+ on the stack at [SP]+; when the
callee is varargs, callee pushes R8..R1 onto the stack creating a vector
of arguments which can be indexed as subroutine consumes one varags after
another..

> So when in a C program you have

> ...
> return foo(...);
> }

> in assembly language this is:

> call foo
> add $96, %rsp ;or something like that
> return

The add $96 is the "subroutine calling foo()" cleaning itself up.

> and tail-call elimination of that is not possible in general.

Prior to control transfer, the stack must be as expected at the entry
point and the local data must already be in its expected place {stack,
registers}. This makes it harder, but not impossible. So, tail call
elimination requires running through the epilogue so you can branch
back to the prologue. If you understand this, you can tail-call to
post prologue code and leave the stack alone.

So, instead of::

foo:
prologue
foo__body:
body
bc foo__epilogue
call foo()
foo__epilogue:
epilogue
RET
one can write:

foo:
prologue
foo__body:
body
bc foo__body
epilogue
RET

The reason it works well and smoothly in LISP and Scheme is that both
languages would be DOA without it.

> gcc has
> something called sib-call elimination ("sib" for sibling), and AFAIK
> this includes tail-recursion elimination, but I expect that even that
> does not work at all times, e.g., because a pointer is passed to the
> called function, and the C compiler cannot prove that it does not
> point to something that is on the stack frame of the caller.

> - anton

On Tue, 09 Jan 2024 07:41:51 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>"Paul A. Clayton" <paaronclayton@gmail.com> writes:
>>I also vaguely recall reading at some point that even
>>recursion that was "easy" to convert to tail recursion was
>>not handled by gcc (also many years ago).
>
>What looks like a tail-call to a Lisp or Scheme programmer actually is
>not when it comes to C. That's because in C calling conventions, the
>caller is responsible for cleaning up the stack, and this aspect of
>the calling conventions is necessitated by the combination of varargs
>and the optionality of function declarations.
>
>So when in a C program you have
>
> ...
> return foo(...);
>}
>
>in assembly language this is:
>
>call foo
>add $96, %rsp ;or something like that
>return
>
>and tail-call elimination of that is not possible in general. gcc has
>something called sib-call elimination ("sib" for sibling), and AFAIK
>this includes tail-recursion elimination, but I expect that even that
>does not work at all times, e.g., because a pointer is passed to the
>called function, and the C compiler cannot prove that it does not
>point to something that is on the stack frame of the caller.
>
>- anton

You can tail-call and continuation-pass in C with the
Cheney-on-the-MTA technique.

https://plover.com/~mjd/misc/hbaker-archive/CheneyMTA.html

TLDR; the idea is to bookmark the stack with setjmp(), allow it to
grow until some high-water mark is passed, then longjmp() to release
it all at once.

YMMV,
George

George Neuner <gneuner2@comcast.net> writes:
>On Tue, 09 Jan 2024 07:41:51 GMT, anton@mips.complang.tuwien.ac.at
>(Anton Ertl) wrote:
>>So when in a C program you have
>>
>> ...
>> return foo(...);
>>}
>>
>>in assembly language this is:
>>
>>call foo
>>add $96, %rsp ;or something like that
>>return
>>
>>and tail-call elimination of that is not possible in general. gcc has
>>something called sib-call elimination ("sib" for sibling), and AFAIK
>>this includes tail-recursion elimination, but I expect that even that
>>does not work at all times, e.g., because a pointer is passed to the
>>called function, and the C compiler cannot prove that it does not
>>point to something that is on the stack frame of the caller.
>>
>>- anton
>
>You can tail-call and continuation-pass in C with the
>Cheney-on-the-MTA technique.
>
>https://plover.com/~mjd/misc/hbaker-archive/CheneyMTA.html
>
>TLDR; the idea is to bookmark the stack with setjmp(), allow it to
>grow until some high-water mark is passed, then longjmp() to release
>it all at once.

Yes, you can implement the aspect that tail calls are guaranteed to be
unlimited in languages like Scheme in that way, but it's not
particularly efficient.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>