Register Assignment Algorithm for Generation of Highly Optimized Object Code

Abstract

A register assignment algorithm is described that, in contrast to traditional methods, permits a high level of optimization at both local and global levels. This involves splitting local register optimization into two phases, with global assignment intervening. Because novel techniques are used in the global assignment procedure, it is described in detail. Experimental results with a prototype implementation are presented in which object code improvements on the order of 25 percent over a production optimizing compiler were obtained. No attempt was made to assess manpower costs of a final implementation nor to weight them against expected improvements in generated code.