Register Optimisation by Equivalence Analysis

Abstract

Traditionally, the register allocation is based on the lifetime analysis of variables. A register can be shared by multiple variables if they have mutually disjointed lifetime intervals. In this paper we attempt to extend the register sharing by another type of analysis called equivalence analysis. After the register allocation by a conventional register allocation algorithm such as left edge algorithm, some incompatible registers can possibly have the same content or their contents can be included in the contents of some other registers in any state of a design. Such registers are totally or partially equivalent and they can be merged into a single register. Our approach offers then a supplement potential for the register optimisation. Hence, it is allowed to go beyond minimisation by lifetime analysis. However, it does not only optimise the number of registers but also reduces the interconnection cost and the number of functional units previously allocated. Therefore, it reduces the implementation cost and improves the design performance.