Minimum Register Instruction Sequencing to Reduce Register Spills in Out-of-Order Issue Superscalar Architectures

R. Govindarajan, H.Yang, J. N. Amaral, C. Zhang, Guang R. Gao

In this paper we address the problem of generating an optimal instruction sequence S for a Directed Acyclic Graph (DAG), where S is optimal when it uses a minimum number of registers. We call this the Minimum Register Instruction Sequence (MRIS) problem. The motivation for studying the MRIS problem stems from several modern architecture innovations/requirements that put the instruction sequencing problem in a new context. We develop an efficient heuristic solution for the MRIS problem. This solution is based on the notion of an instruction lineage --- a set of instructions that can definitely share a single register. The formation of lineages exploits the structure of the dependence graph to facilitate the sharing of registers not only among instructions within a lineage, but also across lineages. Our efficient heuristics to ``fuse'' lineages further reduce the register requirement. This reduced register requirement results in generating code sequence with fewer register spills. We implemented our solution in the MIPSpro production compiler and measured the performance on the SPEC95 floating point benchmark suite. Our experimental results demonstrate that the proposed instruction sequencing method significantly reduces the number of spill loads and stores inserted in the code, by more than 50% in each of the benchmarks. Our approach reduces the average number of dynamic loads and stores executed by 10.4% and 3.7%, respectively. Further, our approach improves the execution time of the benchmarks on the average by 3.2%. In order to evaluate how efficiently our heuristics find a near-optimal solution to the MRIS problem, we develop an elegant integer linear programming formulation for the MRIS problem. Using a commercial integer linear programming solver we obtain the optimal solution for the MRIS problem. Comparing the optimal solution from the integer linear programming tool with our heuristic solution reveals that in a very large majority (99.2%) of the cases our heuristic solution is optimal. For this experiment, we used a set of 675 dependence graphs representing basic blocks extracted from scientific benchmark programs.

Return to José Nelson Amaral's Publications

Send comments to: amaral AT cs DOT ualberta DOC ca

Return to Amaral's home page