This is the mail archive of the 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]
Other format: [Raw text]

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.

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