optimising recursive functions

[Robert Dewar]

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.
> 
> 
>