This is the mail archive of the
mailing list for the GCC project.
proper tail recursion for gcc
- To: gcc at gcc dot gnu dot org
- Subject: proper tail recursion for gcc
- From: Mark Probst <schani at mips dot complang dot tuwien dot ac dot at>
- Date: Thu, 20 Jul 2000 02:03:57 +0000
i want to implement proper tail recursion for a much broader set of
cases than is currently implemented.
motivation: people using gnu c as a portable assembler suffer from the
fact that there is no way to make gcc do proper tail recursion. as a
result, some scheme compilers (bigloo, stalin and hobbit, which is
used by guile) are not standard compliant (scheme requires proper tail
recursion) and at least one prolog compiler (gnu prolog) has switched
from generating c code to assembler, making it non-portable (it is
currently only avaible for x86 and sparc). the prolog-like mercury
has to jump through some (non-portable) hoops to use gcc as an
efficient assembler. the currently available tail call optimization
in gcc does not go far enough, especially in that it does not permit
separate compilation (tail-callees must be static).
proposal: i want to implement a construct for tail calls. this could
either be in the form of a modifier for the return statement or a new
language construct, i.e.
return __tailcall__ f(a,b,c);
suggestions regarding the syntax are welcome. there are several
reasons for doing it this way. the alternatives would be:
* analysis within the compiler regarding which tail calls can be made
proper. the problem with this approach is that there might be a lot
of badly behaving code in existance that assumes that tail calls are
not proper. furthermore, there would have to be sharp and easily
satisfyable constraints on the c code of the caller or else there
would be no way to make sure that tail calls really are proper.
* declaration of tail-callees. using this approach it would still be
necessary to analyze the code in order to determine whether a given
tail call could be made proper. hence, all above mentioned problems
apply here also.
* functions with variable arguments could not make proper tail calls.
i'd like to implement this feature for at least the alpha and x86
do you have any suggestions? anything i should look out for?