Path: utzoo!attcan!uunet!amgraf!cpsolv!rhg
From: rhg@cpsolv.UUCP (Richard H. Gumpertz)
Newsgroups: comp.sys.m88k
Subject: Re: Register Allocation (was Re: Info about 88open & standards)
Message-ID: <455@cpsolv.UUCP>
Date: 24 Nov 89 19:50:09 GMT
References: <1989Nov16.212149.9770@paris.ics.uci.edu> <100050001@hpcuhc.HP.COM>
Reply-To: rhg@cpsolv.uucp (Richard H. Gumpertz)
Organization: Computer Problem Solving, Leawood, Kansas
Lines: 44

THESIS 1: The caller knows what registers are live; the callee does not. 
Hence the caller should decide what needs saving. 

THESIS 2: The callee knows what registers he clobbers; the caller does
not.  Hence the callee should decide what needs saving. 

In other words, if the caller and callee are presumed to be compiled
separately, neither has enough information to do the "right" thing with
respect to register-saving.

By splitting the registers in two classes, "leaf" (i.e., callees that
never call anything) procedures can try to use just the clobberable
registers and so avoid any register saving.  Similarly, "root" (i.e.,
callers that are rarely called) can try to use just the preserved
registers and so avoid saving anything around calls.

Procedures that both do lots of calling and are called frequently are in
a middle ground: that is where the compiler will have to work to figure
out what goes in which register.  Certainly not an easy task, but it can
be done.  Here is where the compiler writer should earn his keep.  By
the way, note that a smart compiler might even save registers around a
block or loop of calls instead of around each call.  Still, in many
cases it will just be a trade-off between saving on entry and saving
before calling out.  If both are done with equal AVERAGE frequency (i.e. 
the procedure makes one call out, average, per time that it is called),
it doesn't matter to execution speed which is used.  (Code size may be
effected, but in RISC architectures the decision has already been made
to increase speed at the cost of ignoring code size anyway.)

Clearly the OVERALL average across ALL procedures MUST be one call out
per call in.  The question is, what does it look like for a particular
procedures?  What is the distribution of called/call ratios?

I personally think some sort of split of register saves is reasonable. 
Only measurement can tell whether 50-50 is appropriate for a particular
level of compiler intelligence and program mix.  Still, it's as good a
place to start as any. 


-- 
===============================================================================
| Richard H. Gumpertz rhg%cpsolv@uunet.uu.NET -or- ...uunet!amgraf!cpsolv!rhg |
| Computer Problem Solving, 8905 Mohawk Lane, Leawood, Kansas 66206-1749      |
===============================================================================