Re: Caller/Callee saved Registers

I was going over the past discussion on Caller/Callee saves and noticed
that nobody mentioned the following...


Henry Baker referred to Guy Steele's paper "Dream of a Lifetime:..." in
the 1980 LISP conference. Steele's idea quickly degenerates to a callee
saves scheme with additional overhead.


Steele's idea is to save the intersection of the registers that the caller
and callee require. This might sound simple but to compute the
intersection, it is necessary to propagate the "required" registers down
the call hierarchy. for example,


      at some point in the call chain, A calls B.
      B will save all registers that lie in the intersection of
                registers that B requires and
                registers that A requires


The key point is that the registers that A requires also includes those
registers that *its* caller requires but A did not save because it did not
lie in its intersection.


Fairly large procedures require fairly large number of registers. While
propagating the union of registers, the set quickly approaches the
universal set of registers available. Hence, when the callee performs an
intersection, it is merely an operation against the universal set which,
in effect, is a pure callee saves approach. The overhead is that the sets
have to be passed on to procedures and the time taken to perform the union
and intersection operations.


The above argument was partially stated in the following
dissertation:


@phdthesis{McKMK84-214,
  author = "McKusick, ${}^{\surd}$Marshall Kirk",
  title = "Register Allocation and Data Conversion in Machine
Independent Code Generators",
  school = "University of California, Berkeley",
  address = "Computer Science Division, Berkeley, CA",
  month = sep,
  year = 1984,
  note = "Also techreport UCB/CSD-84-214",
}


Hope this either answers or clarifies the queries of the
following people...




alk@et.msc.edu (Anthony L. Kimball) Wrote on Wed, 23 Mar 1994:
!Contra M. Beusterien, I feel it is an architectural issue in as
!much as it is a problem most appropriately solved by throwing
!hardware at it: The obvious architectural solution seems to be for
!the caller to set a use mask, for the callee to set another
!use mask, and for the processor to do a save of the intersection,
!with special-purpose logic. Anything like this out there?


robertsw@agcs.com (Ye Wilde Ryder) Wrote on Wed, 23 Mar 1994:
!I've often thought the solution to this problem could easily be solved in
!hardware. A call instruction that indicates which regs need saving in a
!bitmask could be combined with a stack-frame-creation instruction
!(similar to the mc68k family's link instr.) that logically ands this
!bitmask with another bitmask that indicates which regs the routine needs
!to trash. The result of this logical and would be the actual regs that
!need saving. This could all be done in software, but it would be far
!more efficient in hardware.
!
!so why hasn't this been done yet?


Peter-Lawrence.Montgomery@cwi.nl (Peter L. Montgomery) Wrote on 24 Mar:
! Suppose A calls B, which calls C in a loop.
!
! A needs registers 1 and 2 and 5 saved past the call to B.
! B uses 2 and 3, but needs nothing saved past the call to C.
! C uses 1 and 3 and 4, calls nobody.
!
!Who saves register 1? More precisely, what mask does B pass to C? If


---------------------------------------------------------------------------
Nandakumar Sankaran (nandu@cs.clemson.edu) (nsankar@hubcap.clemson.edu)
311-8 Old Greenville Hwy. Clemson SC 29631-1651 (803)653-7749
G34 Jordan Hall Comp. Sci. Dept. Clemson Univ. SC 29634 (803)656-6979
--

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