Optimal Register Saturation in Acyclic Superscalar and VLIW Codes

Abstract : In a previous work [TT00], we theoretically studied the register saturation notion in the acyclic data dependence graphs (DDG). It consists in computing the exact maximal number of the registers needed to achieve the computation of the DDGs independently from the schedules. We proved that this problem is NP-complete and we proposed a greedy heuristic to solve it. In this work, we study how to compute the optimal solution using the integer linear programming. Also, new theorems are given to formally prove some of our assertions written in the previous report. We prove also that the problem of reducing the register saturation by introducing new arcs is an NP-hard problem, and we give a method to compute the optimal solution using the integer linear programming.