Re: Caller/Callee saved Registers

bart@cs.uoregon.edu (Barton Christopher Massey) writes:
> One additional point about caller vs. callee save which I'm surprised no
> one has mentioned: callee-save makes it rather more difficult to implement
> tail-call optimization.


John McClain <pdp8@ai.mit.edu> wrote:
> Callee-save does not make tail-call optimization more difficult. The
> procedure making the tail-call needs to first get rid of everything it put
> on the stack (in the process restoring any of the callee-save registers it
> used.) This is what makes it a properly tail recursive call. The called
> procedure can do anything with the stack it wants. Would you say an
> implementation was not properly tail recursive if some procedure that was
> tail-called temporarily spilled some registers to the stack? The
> situation with callee save registers is analogous.


I'll admit I glossed over the fact that in many situations callee-saves
still allows tail-call. I think it is a necessary condition, though, that
any registers passed as arguments to the tail-called procedure needn't be
saved by the tail-caller. A program which violates the condition is


# callee-saves, args in r0..rn
# all non-arg registers must be preserved
f: # 1 arg
push r1
add r0,1,r1
call g # 2 args
pop r1
ret


I can't see how this could be rewritten into a tail-call, inasmuch as r1
*must* be restored even though f is never going to use it again (f's
caller might), and r1 *cannot* be restored until g has finished, because
it's an argument to g. Given caller-saves, however, we could simply
scribble on r1 and not save and restore it.


IMHO the easiest fix which allows tail-call of all procedures in tail
positions, given this condition, is to mandate that all registers should
be caller-saves. It's true that scratch registers which will never be
used to hold arguments can still be callee-saves without too much grief --
they can be restored immediately before the tail call, as you state. And
if there are registers to burn, or with an entirely memory-based argument
passing convention, unused argument registers need not be saved at all!
But, all in all, I'll still stick by my statement that callee-saves makes
tail-call "rather more difficult to implement" :-).


[Incidental question: Somebody out there must have done studies on whether
call-by-value argument registers should be preserved or should be used as
scratch registers once their value has been extracted. I'm guessing the
answer is that using them as scratch is almost always the right thing, but
that's just a guess. Anybody have a bibliography handy which cites
answers to this?]


>> This is a very valuable optimization for recursive programs...
> It does not matter so much for recursive programs, if they are
> tail-recursive then for most people, most of the time it is
> just as easy to use/read a for/while/until loop.


No, I think the interesting case is not simple tail-recursion, but complex
patterns of deep recursion. Consider, e.g., a recursive-descent parser:
the only way to "use a while loop" that I know of is to recode the parser
as table-driven LL, which is arguably the right thing if one can do it
:-), but not necessarily possible or desirable in all situations.
Tail-call, on the other hand, will get rid of most of the return stack
"for free".


> The lack of tail-call optimization really hurts if you want
> to use a continuation passing style of programming.


Yes! C semantics appear at first glance to allow a continuation-passing
style using function pointers (albeit casts must be used to shut up the
type system :-), but unfortunately most existing implementations don't
implement tail-call, and so eventually the return stack fills up.


Bart Massey
bart@cs.uoregon.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.