This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

proper tail recursion for gcc


hi

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);

or

	__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.

limitations:

* functions with variable arguments could not make proper tail calls.

i'd like to implement this feature for at least the alpha and x86
architectures.

do you have any suggestions? anything i should look out for?

bye
schani

-- 
Mark Probst
Student, Programmer
http://www.complang.tuwien.ac.at/~schani/

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]