Path: utzoo!news-server.csri.toronto.edu!rutgers!usc!zaphod.mps.ohio-state.edu!mips!mash
From: mash@mips.com (John Mashey)
Newsgroups: comp.arch
Subject: Re: register save
Message-ID: <912@spim.mips.COM>
Date: 12 Mar 91 02:23:20 GMT
References: <1991Mar11.192116.1974@dgbt.doc.ca>
Sender: news@mips.COM
Organization: MIPS Computer Systems, Inc.
Lines: 79
Nntp-Posting-Host: winchester.mips.com

In article <1991Mar11.192116.1974@dgbt.doc.ca> don@dgbt.doc.ca (Donald McLachlan) writes:
>	The idea of saving the return address in a register, rather than
>on the stack sounds nice to me, but ...
>	This requires that the calling function knows that the called
>function is a leaf function, not very practical from a high level language
>point of view as far as I can tell.
>
>	The only way I can think to generalise this would be to always
>put the return address in a dedicated register. This would require that

1) Many RISCs around do this, i.e., use the moral equivalent of
the S/360 BRANCH-AND-LINK instruction.

2) The callee:
	a) Saves the return address register (for sure)
OR
	b) The callee (if a leaf, and it certainly knows that)
	never saves the return address register
OR MAYBE
	c) If the callee has "leaf paths", ie.., ones where it doesn't
	call other subroutines, even though it has some where it does, the
	compiler may choose to rearrange the save/restores to avoid them
	on some of the paths where they would be unnecessary.  (Some compilers
	do this, i.e., cc -O3 on MIPS, for example, in certain cases.)

3) AS has been posted here in the past, it has been observed that
the number of registers saved/restored per function call can be kep
small (like about 2, on the average, for suites of programs of
SPEC-like nature), if:
	a) You have a good optimizer with a good register allocator.
	b) You have ENOUGH registers that a reasonable number (say 50%)
	can be made scratch (caller save).  Typically, enough == 20..32
	available for general use.

4) In many environments, the frequency of leaf routines is high,
on the order of 50%.

5) There is plenty of analysis of this topic in Hennessy and Patterson,
including detailed statistics about the effects of more registers
and/or better optimization.

6) On any MIPS-based machine, assuming that it includes pixie, prof,
and pixstats (most do), it is trivial to this kind of analysis:
do:
	pixie  program		creates program.pixie
	program.pixie		run it
	pixstats program	getthe statistics
and look for the section that lists the number of callee-saved
registers saved/restored: this is a table that goes from 0 to 10.
Perhaps easier, look for the line labeled "Average registers saved
per entry:"

To get % of calls to leaf routines is a little harder, but one of the
"prof" sections gives the number of calls to each function,a
and the percentage of total, although it doesn't identify whether
something is a leaf or not.  Also, this begsthe question of whether
or not something is clearly a leaf (i.e., zero calls to other functions),
or dynamically a leaf (i.e., some calls of it do NOT cause it to call others;
there are compilers that can move register save/restores around to
sometimes avoid saving them when unnecesary).

7) Finally, the really crucial thing in all of this is to understand
how big a percentage of run time is spent in subroutine call overhead,
and THEN, and ONLY THEN figure out if it's worth a lot of hardware
to do something about it, especially if that hardware is very difficult
to pipeline.  The evidence, so far, is that good compilers plus enough
registers get rid of an awful lot of the overhead.  One can argue,
or not, about whether register windows get rid of enough more to be
worth it.  Certainly, I'd prefer register windows to complex function
call instructions. Among other things, in looking at RISC code,
in which instructions are frequently re-ordered, I've quite often seen
the pieces of the subroutine call mechanism spread all over a piece of
code, in ways that fill cycles that would otherwise be stalls,
and in sequences for which hardware is unimaginable...
-- 
-john mashey	DISCLAIMER: <generic disclaimer, I speak for me only, etc>
UUCP: 	 mash@mips.com OR {ames,decwrl,prls,pyramid}!mips!mash 
DDD:  	408-524-7015, 524-8253 or (main number) 408-720-1700
USPS: 	MIPS Computer Systems MS 1/05, 930 E. Arques, Sunnyvale, CA 94086