Fri, 28 Oct 1994 17:00:41 GMT

Related articles |
---|

How common is this register use optimisation? u31b3hs@POOL.Informatik.RWTH-Aachen.DE (1994-10-28) |

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:

- 1 for loading a constant

- 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

for faster access to frequently used variables. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.