Re: Register optimizations

Before this guy gets his head flamed off I'd like to add a comment
or two.


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.


I know there is a ton of literature on this but it would be nice if
there were a suggestion or two for where a relative beginner should
start. Many of us wrote 'tiny' compilers in school that generated
assembly code and could be used for real problems. What would be
a managable next step for improving these compilers and learning
a little more about register allocation and code optimization?


: 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?


The dragon book has a good algorithm for register allocation for
a single expression, that is as long as you're not doing common
subexpression elimination. It handles the case where you run out
of registers and must begin using temporaries on the stack. A very
simple extension to this is (assume your machine has 32 registers):


1. Allocate 10 registers for 'register' variables.
2. Do a simple scan of the intermediate code and allocate
the registers to the 10 most referenced locals. You can
keep a bit in the symbol table indicating that
a variable's address had been taken. Skip these.
3. In the dragon book algorithm, forget that these 10
registers exist when allocating registers for intermediate
values.


Just this minor addition to a simple compiler is likely to triple
or quadruple the speed of many programs.


Other managable additions:


1. Pass the first few function arguments in registers.
2. You can shadow local variables in registers by:
a. When you store a register into a local you
associate that register with the local. Arrange
to make this register the LAST one allocated for
temporaries in expressions.
b. If you need to re-use the register for another
expression, forget the information you saved in (a).
c. If the rvalue of the local is requested before the
register is trashed by (b) then you can use
the register, saving a load from the local.
You need to forget all register/local associations
if you branch or make a function call.


Any other >simple< suggestions?


: The problem I see with approach #1 is that it can't be used for any
: variable that could ever be referenced by address; the register obviously
: has no address, and thus that variable would have to be left in main
: memory. However #2 seems like it wouldn't be as effective an optimization,
: as loading a value from a register offset is slower than a simple push/pop.


: Or, is there some other, better approach I haven't yet run across?
: Suggestions welcome, and thank you for your time.


It'd be interesting in knowing what others feel (from experience)
are the classic optimizations worth pursuing for the hobbyist/hacker. Put
another way, if you had to limit your optimizer to 1000 lines of
code what strategy would you choose?


Bob
--

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