Re: Caller/Callee saved Registers

pmagun@iiic.ethz.ch (Paul Jakob Magun) writes:
>[Why divide in to caller-save/callee save?
> Won't this be worse than global (interprocedural) allocation?
> What if all regs were caller-save or callee-save?
> How do designers decide how many caller/callee to use?
> Why no callee-save parameter registers?]


Register sets are divided in to caller-save and callee-save because you
have to save and restore registers sometime and because procedure
boundaries seems like a good place to do it. Yes, interprocedural
allocation can give better save/restore but (a) interprocedural allocation
is more expensive (b) can't be parallelized as easily and (c) can't always
be done (e.g. dynamic liniking; you can't do caller register allocation
for a callee that doesn't yet exist) so you have to have a back-up anyway.


If all regs are caller-save, then callers may save and restore registers
that the callee never uses. Even if the callee uses the registers, each
caller has to have code to save and restore those registers. By contrast,
if all registers are callee-save, then only those registers that are used
by the callee actually get saved and restored, and the code to do so is
concentrated in one place (the callee, rather than being duplicated in
each caller). However, the callee may save and restore registers that are
`dead' -- that is, registers that will be set by the caller before they
are read by the caller.


How do you decide what's the best division? The best description that
I've seen is that some registers tend to be dead at every call site and
few procedures use all registers (directly; most registers get used sooner
or later) and that empirically 1/2 caller-save 1/2 callee-save works well.
If you believe that most leaf functions are small, then most leaf
functions will not use all registers, so a strict caller-save policy will
behave badly (e.g. useless spills and restores) and will waste code space
(and locality) by performing spills and restores in each caller instead of
in the callee. If you believe there are some dead registers at each call
site then full callee-save will behave badly (e.g. useless spills and
restores). Note that some optimizations can change the profitability of
each strategy and that e.g. better inlining of small routines tends to
reduce the relative costs of either scheme (by reducing the frequency of
calls). Sorry, I can't point you at definative studies.


Callee-save parameter registers could be useful if, say, several routines
are called with the same parameters and/or one routine is called
repeatedly with most of the same parameters. However, making good use of
these registers would require the caller and callee to agree in some way
on which parameters should be passed in which registers. I think the
decision to just use caller-save registers is based on simplicity and
common use patterns.


;-D on ( The square dance caller ) Pardo
--

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