Re: Tail recursion

fjh@cs.mu.OZ.AU (Fergus Henderson)
21 Aug 2000 00:00:10 -0400

          From comp.compilers

Related articles
Tail recursion strohm@airmail.net (2000-08-10)
Re: Tail recursion pfaffben@msu.edu (Ben Pfaff) (2000-08-13)
Re: Tail recursion danwang+news@cs.princeton.edu (Daniel C. Wang) (2000-08-14)
Re: Tail recursion toon@moene.indiv.nluug.nl (Toon Moene) (2000-08-14)
Re: Tail recursion fjh@cs.mu.OZ.AU (2000-08-21)
Re: Tail recursion Wilco.Dijkstra@arm.com (Wilco Dijkstra) (2000-08-21)
Re: Tail recursion mrs@kithrup.com (2000-08-21)
Re: Tail recursion ian0kerr@my-deja.com (2000-09-08)
Tail recursion Alexey.Mikhailov@gmail.com (jjb) (2006-11-04)
Re: Tail recursion kym@ukato.freeshell.org (russell kym horsell) (2006-11-04)
Re: Tail recursion diablovision@yahoo.com (2006-11-05)
[2 later articles]
| List of all articles for this month |
From: fjh@cs.mu.OZ.AU (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 <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.


Post a followup to this message

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