Dan Sugalski wrote:
> Benjamin Goldberg wrote:
>> Jason Gloudon wrote:
>>> Piers Cawley wrote:
>>>
>>>>> I think you're overlooking the "restoreall" done just before
>>>>> the jump-no-save-returnaddress operation... I see two "saveall"s
>>>>> and two "restoreall"s.
>>>>
>>>> But with proper tail call optimization you'd only need *one*
>>>> saveall. That's why it's an optimization.
>>>
>>> Tail call optimization is a space (stack size) optimization. The
>>> scheme definition only requires space efficiency. The time
>>> optimization is important but a secondary consideration for the
>>> functional language folks.
>>
>> Here's an idea -- considering that the first op of every sub seems to
>> be a 'saveall' instruction,
>
> If that's true, we need to thump IMCC some. There's no reason for
> this to be the first op--if the caller wanted any registers saved it
> had darned well beter have taken care of it itself. That's the point
> of caller-save, after all...
Erm, my statement was actually just an assumption that the first op
would be a 'saveall' -- I haven't looked at actual imcc output. By your
comment, I'll assume that my earlier assumption was wildly wrong.
-------
Is it possible to divide subroutines into two groups, caller-save and
callee-save? If so, then I *think* that we should be able to make at
least *some* tail-optomizations:
If a caller-save subroutine is going to return the results of another
caller-save subroutine, the first can jump directly into the other.
If a callee-save subroutine is going to return the results of another
callee-save subroutine, the first can jump to the Nth opcode of the
second subroutine, in the manner described down below.
In the other cases (callee-save going to caller-save, or vice-versa), I
suppose (but might be mistaken) that the only tail-call optomization
that can be done is to have the caller skip the step of removeing
results from the stack and then pushing them back on... which might
already be done.
---------
There's three or four ways that I can think of for an ordinary
callee-save subroutine to work:
1/ saveall/restoreall
2/ push[ipns]/pop[ipns]
3/ push/pop (with the help of rotate_up)
4/ a combo of 2 and 3.
I assume that most callee-save subroutines have the following stages:
1/ save the registers we're going to be dirtying
2/ (optional, use with methods 3&4 mentioned above)
rotate_up the stack so that our arguments are on the top.
3/ pop the arguments into registers
4/ do our work
5/ push the return values onto the stack.
6/ (optional) rotate_up the stack
7/ restore the registers we've dirtied.
8/ pop an address off the stack and goto it. (op "ret")
If a caller is going to perform a tail-optomized function call, then it
could look like:
1/ save the registers that the callee is going to restore in the
callee's step 7
2/ save any registers that we're using that weren't already saved
3/ rotate_up the stack, if step 2 used "push" ops.
4/ pop the arguments into registers.
5/ do our work
6/ copy the callee's arguments into whatever registers the callee
would put them into in the callee's step 3.
7/ restore the registers that were saved in our step 2.
8/ branch to step 4 of the callee.
It may be possible for the caller to avoid an explicit step 6, if it can
have it's computations put the arguments in the target registers
directly.
Note that steps 2,7 of the caller can't use saveall/restoreall, since
that would interfere with the registers written to in step 6. (If you
do want to use saveall/restoreall for 2,7, then step 6 becomes "push the
arguments for the callee onto the stack", and step 8 becomes "branch to
step 3 of the callee"). Similarly, if the callee puts arguments into
integer (etc.) registers, you probably can't use savei/restorei.
--
$;=qq qJ,krleahciPhueerarsintoitq;sub __{0 &&
my$__;s ee substr$;,$,&&++$__%$,--,1,qq;;;ee;
$__>2&&&__}$,=22+$;=~y yiy y;__ while$;;print
