Re: Tail recursion (Fergus Henderson)
21 Aug 2000 00:00:10 -0400

          From comp.compilers

Related articles
Tail recursion (2000-08-10)
Re: Tail recursion (Ben Pfaff) (2000-08-13)
Re: Tail recursion (Daniel C. Wang) (2000-08-14)
Re: Tail recursion (Toon Moene) (2000-08-14)
Re: Tail recursion (2000-08-21)
Re: Tail recursion (Wilco Dijkstra) (2000-08-21)
Re: Tail recursion (2000-08-21)
Re: Tail recursion (2000-09-08)
Tail recursion (jjb) (2006-11-04)
Re: Tail recursion (russell kym horsell) (2006-11-04)
Re: Tail recursion (2006-11-05)
[2 later articles]
| List of all articles for this month |

From: (Fergus Henderson)
Newsgroups: comp.compilers
Date: 21 Aug 2000 00:00:10 -0400
Organization: Computer Science, University of Melbourne
References: 00-08-054 00-08-071 00-08-089
Keywords: optimize

>Ben Pfaff <> 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" <> 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 <> | "I have always known that the pursuit
WWW: <> | of excellence is a lethal habit"
PGP: finger fjh@ | -- the last words of T. S. Garp.

Post a followup to this message

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