On the Optimality of Register Saturation

In this paper, we continue our theoretical efforts and we present two main results. First, we give an exact solution with integer linear programming for both the problems of computing the RS of a DAG and reducing it. Our integer program brings a new way to model register constraints that allows us to produce the lowest number of constraints and variables in the literature (till now). Indeed, given a DAG with n nodes and m arcs, we need O(n2) integer variables and O(m+n2) linear constraints, which is better than the actual size complexity in the literature that model register constraints. Second, we prove that the problem of reducing the register saturation is NP-hard. Our detailed experiments in this paper show that our previous heuristics [Sid-Ahmed-Ali Touati. Register Saturation in Superscalar and VLIW Codes. In Proceedings of The International Conference on Compiler Construction, Lecture Notes in Computer Science. Springer-Verlag, April 2001] are nearly optimal. We provide a discussion too in order to argument why the RS approach should be better that minimizing the register requirement.