Re: Register optimizations

baynes@ukpsshp1.serigate.philips.nl
Wed, 8 Mar 1995 07:41:50 GMT

          From comp.compilers

Related articles
Register optimizations ArielMars@aol.com (1995-03-02)
Re: Register optimizations mercier@news.cinenet.net (1995-03-05)
Re: Register optimizations baynes@ukpsshp1.serigate.philips.nl (1995-03-08)
Re: Register optimizations torbenm@diku.dk (1995-03-09)
Re: Register optimizations preston@tera.com (1995-03-12)
Re: Register optimizations anton@mips.complang.tuwien.ac.at (1995-03-16)
Re: Register optimizations conway@munta.cs.mu.OZ.AU (1995-03-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: baynes@ukpsshp1.serigate.philips.nl
Keywords: registers, optimize
Organization: Compilers Central
References: 95-03-025
Date: Wed, 8 Mar 1995 07:41:50 GMT

Seeing as none of the experts have taken this up, I will have a go.


ArielMars@aol.com wrote:
: I've been looking at a number of methods of using registers to speed up
: expression execution. It seems that great use could be made of registers,
: especially on RISC machines with lots of them available.


Thats why they give them lots of registers.


: Perhaps some of you with some experience could help me answer this one. As
: compared to a system in which all local variables are held on the stack,
: and where a single register is used to store the current value being
: operated on and intermediate expression results are pushed on the stack,
: is it more efficient to:


: 1) remap commonly used variables into registers, just use the one register
: for expressions, and use stack space for intermediate values; or,


: 2) leave the local variables on the stack, and use registers for all
: intermediate expression values?


Any remaining registers are used for variables.
If you are just restricted to one of your choices then unless you have a very
fast push and pop onto the stack I would expect 2 to be much more efficient.
Using a register for a variable rather than an intermediate value would only
give a gain if the variable is very heavily used or very few expressions
would use that register for an intermediate value.


Most compilers will use a combination of these. For example to give priority
to using registers for intermediate values (and if not enough registers then
use the stack as well). Any remaining registers are used for variables.


However one can do better than just simply deciding to dedicate a register
to a single variable. One can perform a live variable analysys to find out
when one actually needs to know the value of a variable. This is done
by propagating backwards the information that a value is needed for a
variable. (It is also normal to propagate forward the information that a
value is available in a variable as well. This can pick up use of
uninitialized variables.)


For example:
                                                A is dead (not needed)
                a = 3;
                                                A live (has a value that is needed)
                b = 4 * a;
                                                A is dead (value not needed, though has a value).
                a = x + 1;
                                                A live (has a value that is needed)
                c = a + 1;
                                                A is dead (value not needed, though has a value).


Thus we only need to provide a register (or stack space) when the variable
is live.
This can be extended to provide for live-in-register and live-in-memory
information. One normally has to be a bit pesimistic about live-in-memory.
For example if one gets a value by dereferencing a pointer then any variable
that the pointer might point to has to be regarded as needed in memory.


The next improvement is to forget (as far as possible) and to track the
values assigned to them. For example the value x+1 assigned to a in the third
line of the example above can be tracked to its use in the line below. The
fact that variable a was the transfer mechanism is discarded allowing
extra flexibility in register asignments.


Any reasonable book on compilers will go into some of the algorithms in more
detail.


--
Stephen Baynes baynes@mulsoc2.serigate.philips.nl
Philips Semicondutors Ltd
Southampton
United Kingdom
--


Post a followup to this message

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