Re: Caller/Callee saved Registers

zsh@cs.princeton.edu (Zhong Shao) writes:
>We have recently written some papers on how to make good use of
>callee-save registers in compiling functional languages (e.g., ML)...


I heartily recommend these papers.


>Tail-recursions can be implemented more efficiently in callee-save
>registers than on the stack.


This is actually a very important point. Consider iterative factorial,
which I show in C for the prefix-impaired:


int fact1(n,r) int n,r; { return (n==0?r:fact1(n-1,n*r)); }


int ifact(n) int n; { return fact1(n,1); }


If this is implemented in proper tail-recursive fashion, and if the
function 'fact1' is recognized as being a constant, locally-known function
capable of being in-lined, then ifact should compile into virtually the
same machine code as the following C-weenie version:


int ifact(n) int n; { register int r=1; for(;n;n--) r*=n; return r; }


In the tail-recursive version, both n & r are kept in registers, and never
move (are never saved and/or restored). Thus, the n-1 becomes an
'in-place' decrement, and the n*r becomes an 'in-place' multiplication.


Thus, so long as you don't run out of registers, the overhead of tail
recursion is _independent_ of the number of arguments, and essentially
identical to the imperative code.
--

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