Path: utzoo!attcan!uunet!aplcen!uakari.primate.wisc.edu!gem.mps.ohio-state.edu!usc!cs.utexas.edu!oakhill!phillip
From: phillip@oakhill.UUCP (Mike Phillip)
Newsgroups: comp.sys.m88k
Subject: Re: Register Allocation (was Re: Info about 88open & standards)
Message-ID: <2652@bushwood.oakhill.UUCP>
Date: 21 Nov 89 20:40:43 GMT
References: <1948@psueea.UUCP> <1989Nov14.175806.23483@paris.ics.uci.edu> <1989Nov20.205338.11760@paris.ics.uci.edu>
Organization: Motorola Inc. Austin, Tx
Lines: 113

In article <1989Nov20.205338.11760@paris.ics.uci.edu>, rfg@ics.uci.edu (Ron Guilmette) writes:
> In article <2647@bushwood.oakhill.UUCP> oakhill!bushwood!phillip@cs.utexas.edu (Mike Phillip) writes:
> >
> 
> >    This is where things get tricky...  The key point to recognize is that
> >regardless of compiler technology, there will likely always need to be a
> >distinction between caller and callee saved registers.
> 
> Yes.  The distinction is valuable.  It is needed so that I can tell you
> what type of saving convention is harmful.  "Caller saving consider
> harmful!"

       [deletion of point/counterpoint discussion]
> 
> >    At the other extreme, if all registers were used in "callee save"
> >mode ... the callee
> >would generate load and store instructions for every register that it
> >uses, regardless of whether such overhead is warranted by the "live" use
> >of the same register in the caller.
> 
> Right, but you are still begging the question and avoiding the issue.
> What if the saves & restores are *always* warranted by virtue of the
> fact that *all* registers contain live values at *all* points?  In that
> case, there would be no unnecessary loads or stores in a strictly
> callee-saves convention.
> 
> What I'm having trouble understanding is why various people (Mike P.
> included) seem to be unwilling to accept that this convention (used
> for decades on CICS machines) may actually be simply *the* best possible
> convention, regardless of whether or not you seem to have lots of registers
> to waste or whether or not you have a reduced instruction set.
> 

   You have asked for a situation where "caller save" registers actually
   provide better performance than "callee save" registers...  Consider
   the following situations:

   1)  In a language such as C, where "arbitrary" indirection is
       supported, there are often cases where registers MUST be presumed
       dead across function calls because the values they contain are
       "pointed to" by other variables.  For example, in the following
       code...

               int x;
               int y;
               extern void foo();
                  .
                  .
                  .

       /* Assume at this point that x and y have been placed in registers */

               y = x;
               foo (&x, &y);	
               if (x == y ) {
                  x =  x + y;
               } else {
                  x = x - y;
               }

       Effect on the caller:

       In such a case, the registers containing x and y are effectively
       treated as "caller save" by NECESSITY (assuming that foo is an
       external subroutine) because x and y must be presumed "clobbered"
       across the call.  The contents of the registers
       holding the value of x and y MUST be stored back into the "home"
       memory locations for x and y before the call to foo() because the
       addresses of x and y are passed as parameters.

       Effect on the callee:

       If foo() happens to be a leaf routine (which roughly half of
       all dynamically measured subroutine calls are...), 
       there is NO chance that it will call
       another subroutine.  Thus, the choice of registers is independent
       of subsequent nested calling sequences.  If, as in your scheme, all
       registers are treated as "callee save", spill code must be
       generated for EACH register that is used in the callee.  In a code
       sequence like that shown above, it is POSSIBLE that some of the
       registers selected for use by foo()
       have already been freed by the caller, thus making the callee
       spill code redundant.  In other words, if the compiler had a
       convention for prioritizing register usage based on a GUARANTEE
       that a certain set of registers were available without the need
       for spill code... more efficient code may result.

    2) OCS was not written just for C programs.  In Fortran code,
       anything declared in a COMMON block must be presumed dead
       across calls.  Fortran also handles arrays differently than C,
       which affects calling sequences...
       
    Thus, there are LOTS of situations where "spill"
    code must be inserted by the compiler before a subroutine call.
    If the registers being "spilled" are "caller save" then this
    overhead is not duplicated in the callee... i.e. a good compiler
    may place aliased (or global) variable contents in "caller save" 
    registers.

    Key point ====>  I'm NOT advocating either extreme of the CALLER
    vs. CALLEE spectrum.  I'm simply trying to point out why there
    may be some merit in a caller/callee split.  I would agree that
    in a "perfect" programming world where all subroutines are visible
    to the compiler that the distinction becomes unnecessary.
    Unfortunately, as you pointed out, this is NOT the case, and I
    don't feel that the issue is as clear cut as you state it...

    Further discussion of this probably belongs in comp.compilers or comp.arch.


    ---------------------
    Mike Phillip
    Motorola 88000 Development