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