[fpc-devel] Tail recursion optimization

[Florian Klaempfl]

Jonas Maebe wrote:
>> The recursive call is usually inside an if anyways so the ssa
>> optimizer is lost
>> anyways, no?
> 
> For the part inside the if: yes. But not for the part coming before it.
> What's more important however is that goto/label not only removes the
> usage of SSA, it also means that all register variables are allocated at
> the start of the function and only freed at the end. Without goto/label,
> register variables are only allocated between their first and last use
> (usage in a loop means allocation until the end of that loop).

Practical argument:
the assembler code _is_ better for the code I tested and up to as twice as fast
as the original one.

Theoretical argument:
- using the tail goto you've one function with one set of variables being active
across the the whole function
- using a recursive call you've at least two sets of variables: the caller and
the callee ones. Though one set is only active at a limited part of the
function, the set of the caller is still in use while the callee is called
though they (the caller variables) are spilled.

> 
>> BTW: Does the assembler optimizer track flag usage? Then we could
>> remove some of
>> the    
>>
>> movl    %esi,%eax
>> incl    %eax
>>
>> like pairs.
> 
> There's a FlagsUsed field in the ttaiprop record which is set to true if
> the flags result of that instruction is used.

I guess it could be used to change to code above to
leal 1(%esi),%eax
?

Or is this slower on some CPUs?