Re: Tail recursion

>Ben Pfaff <pfaffben@msu.edu> writes:
>
>> The GCC compiler suite does tail recursion optimization at least
>> for C and C++ and probably for its other languages as well.


The tail call optimization is done in the GCC C/C++ front ends, not in
the back-end, so it may not be present for other language front ends.


"Daniel C. Wang" <danwang+news@cs.princeton.edu> writes:
>But only "intra-procedurally"
>[... example showing that gcc doesn't optimize mutual recursion ...]


Actually it's even worse than that. As of the most recent official
release (2.95.2), GNU C still has a number of other restrictions on
its tail call optimization, including the following:


- it only optimizes tail calls with an explicit `return',
so it won't optimize e.g.


void foo() { foo(); }


- it won't optimize tail calls in functions with local arrays,
even if the array is not used


- it won't optimize tail calls in functions with local variables
whose address is taken and then used in ways that the compiler
can't analyze (e.g. passed to a non-inlined function, stored
in a global variable, etc.)


The last of these is a difficult problem which in C can't really be
solved just by changes to the compiler. I think it would be a good
idea to extend C with a "tail call" construct whose semantics said
that it ended the lifetime of local variables in the calling function.
This would let programmers (or compilers that target C) tell the C
compiler when it is safe to deallocate local variables. Currently C
doesn't provide any way for the programmer to convey that information
to the compiler, and most of the time it is not something that the
compiler can figure out for itself.


--
Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp.

Return to the comp.compilers page.
Search the comp.compilers archives again.