This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: optimising recursive functions
skaller wrote:
On Fri, 2007-10-26 at 20:26 -0400, Robert Dewar wrote:
skaller wrote:
So I am guessing the Felix version is lucky there are
no gratuitous temporaries to be saved when this happens,
and the C code is unlucky and there are.
Maybe someone who knows how the optimiser works can comment?
One problem with departing from the ABI even on a local level
like this is that it wipes out lots of tools that depend on
ABI compliance for the entire call chain. I suspect the overall
gain is too small to be worth this hit.
By 'tools' I presume you mean functions in the gcc compiler
itself? Or at least tools that examine intermediate language
outputs?
No, and no. I mean run time tools such as debuggers, testing
tools, coverage tools, monitors of various kinds.
In fact, ABI compliance for any ABI with 'caller save' registers
disables tail-rec optimisation, so there is not really any choice
at all but to do this optimisation. A trivial example is a C++
list destructor:
No, tail recursion elimination does not disrupt any of these
tools, since the resulting object code is still ABI compliant.
It is calls that do not follow the ABI that are problematic.
That's a tail recursion. If the destructor caller save registers
are pushed before the recursive delete, and popped afterwards,
the function will kill your program by pushing
lots of registers (including the return address) onto the stack,
for every element in the list. Make a list with a few million
elements (quite common), and you can interpret 'kill' literally:
the program will segfault because it is out of stack.
I think you should assume we all understand elementary issues
like what tail recursion is, and how tail recursion elimination
works.
No stack at all is required to implement this function if you use
an inner wrapper and so make a tail call possible.
Yes, of course, as I say, you should assume we all understand
this elementary principle.