Re: Caller/Callee saved Registers

bart@cs.uoregon.edu (Barton Christopher Massey) writes:
|> 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 see two possibilities:


1) The arguments are caller-saved (this is the case in all C calling
conventions I know): Then you need not save and restore r1 around g,
because f does not use it after g and the caller of f performs its own
saving and restoring if necessary. So, no need to pop r1 and you can
optimize the tail-call.


2) The arguments are callee-saved: Then you need not save and restore
r1 around g, because g does that. Again, no pop r1 and you can
optimize the tail call.


So this is not the problem with tail call optimization in C. So what
is? Why isn't it done?


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


No, there's a much better solution: Instead of converting your EBNF (or
RRPG) to BNF and then to a recursive descent parser, write your recursive
descent parser directly from the EBNF. E.g., { ... } is converted into a
while loop.


John McClain <pdp8@ai.mit.edu> wrote:
|> > The lack of tail-call optimization really hurts if you want
|> > to use a continuation passing style of programming.


Yes, using CPS a threaded code interpreter can be implemented in C: Each
abstract machine instruction is a C function. The registers of the
abstract machine are arguments of the functions. E.g., the abstract
machine instruction foo would look like this (assuming direct threading
and an abstract machine with the registers ip and sp):


void foo(Inst *ip, Word *sp)
/* Inst is a function type defined such that the C compiler does not complain
  * about the use of ip below */
{
        /* do what foo should do: */
        ...
        /* fetch and execute the next instruction: */
        (*ip)(ip+1,sp);
}


Unfortunately, without tail call optimization this does not work long.


- anton
--
M. Anton Ertl anton@mips.complang.tuwien.ac.at
--

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