Minimum Register Instruction Sequence Problem:
Revisiting Optimal Code Generation for DAGs
R. Govindarajan, Hongbo Yang, Chihong Zhang, José Nelson
Amaral, and Guang R. Gao
In this paper we address the problem of generating an instruction
sequence $S$ from a data dependence graph (DDG) that is optimal in
terms of the number of registers used by the sequence $S$. This
problem is closely related to the traditional optimal code generation
(OCG) problem, which minimizes the code length, and is known to be
NP-Complete for DAGs. While traditional code generation methods and
instruction-level parallelism compilation techniques emphasize
exposing parallelism to reduce the code length, there are at least two
execution environments~--- out-of-order issue superscalar processors
and low-power embedded architectures~--- where optimizing the number
of registers used takes precedence, even at the expense of limiting
the amount of instruction-level parallelism exposed at compile-time.
We present two solution methods for the Minimum Register Instruction
Sequence (MRIS) problem. First, we present a heuristic solution
which introduces the notion of {\em instruction lineage} that
facilitates the sharing of registers among instructions within a
lineage and across lineages by exploiting the structure of a DDG.
Our second solution is through an elegant integer linear programming (ILP)
formulation for the MRIS problem.
We compared the number of registers used by our heuristic solution,
with that used in the solution generated by an implementation of the
Sethi-Ullman algorithm, and with the minimum register requirement (MRR)
computed by the ILP method for 852 DDGs extracted from standard
benchmark sets. Our heuristic solution found the optimal solution in
99.4\% of the 671 DDGs where the ILP method found the MRR. For the
remaining 181 DDGs, our heuristic method performed better than
Sethi-Ullman's algorithm in 100 DDGs, and worse in only 6 DDGs.
Return to José
Nelson Amaral's Publications
Send comments to: amaral AT cs DOT ualberta DOC ca
Return to Amaral's home
page