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