# How common is this register use optimisation?

## u31b3hs@POOL.Informatik.RWTH-Aachen.DEFri, 28 Oct 1994 17:00:41 GMT

From comp.compilers

Related articles
How common is this register use optimisation? u31b3hs@POOL.Informatik.RWTH-Aachen.DE (1994-10-28)
| List of all articles for this month |

 Newsgroups: comp.compilers From: u31b3hs@POOL.Informatik.RWTH-Aachen.DE Keywords: registers, optimize, question, comment Organization: Compilers Central Date: Fri, 28 Oct 1994 17:00:41 GMT

Transputers have only three universal registers, organised as a stack,
so good register usage is very important for performance. INMOS
describes a nice way how to reduce the number of needed registers for
evaluating expressions, and I found it to be very effective. Three
registers are indeed usually enough. However, that way should also
work for register machines.

The number of needed registers for an expression is defined recursive.
A little simplified, it is defined as:

- max(depth(left tree),depth(right tree)) for operators if both depths
are different
- max(depth(left tree),depth(right tree))+1 for operators if both depths
are equal
- infinite for a function call (or 3 because there are only three
registers on the stack)

This is only true if the left tree has a greater or equal depth and is
evaluated first. Otherwise the left and right trees have to be swapped.
If the operator is commutative that is fine, otherwise the top of stack
has to be swapped back before the code for the operator. On register
machines that should not be needed; just swap the operands for the
operator.

The point is, if the left node needs 2 registers, and the right one
needs 3 then evaluating left-right needs 4 registers in total (one for
the result of left and three for evaluting right). But evaluating
right-left only needs 3 registers in total (one for the result of right
and two for evaluating left).

Is this a common technique to use in compilers?

Michael
[This sounds to me like the Sethi-Ullman numbering discussed in the Dragon
Book. The PDP-11 only had 8 registers, of which two were reserved by the
architecture, one for the frame pointer, and up to two for register
variables. The remaining 3 registers were plenty -- as I recall the C
compiler failed with an error if it ran out of registers, but I never recall
it doing so.
Way back in the 1960s, in an article in the IBM Systems Journal on
the design of the IBM 360, they said that about 4 registers was plenty for
arithmetic temporaries. The rest of the registers are for addressing and