Summary: The problem of allocating a finite number of hardware registers to evaluate arbitrarily complex arithmetic expressions arises in the implementation of programming language compilers. Traditionally, register allocation has been implemented by using graph-theoretic algorithms. In contrast, we discuss an approach based on direct algebraic manipulation of the expressions for which registers are to be allocated. These manipulations employ simple identities and canonical forms from “program algebra”. The algebraic approach admits a straightforward implementation of the required identities as rewrite-rule program transformations. The use of canonical forms for the intermediate expressions makes it possible to apply the transformations automatically.
The approach we describe offers a number of advantages. The algebraic approach is easy to understand, because expressions are manipulated directly instead of being converted to graphs. Moreover, the algebraic approach can implement efficient register-allocation strategies without sacrificing this understandability, through the use of suitably chosen intermediate canonical forms. Finally, the correctness of the algebraic approach is easy to prove, because the program transformations that perform the manipulations are based on identities from program algebra.