Skip to Main content Skip to Navigation
Journal articles

On the Optimality of Register Saturation

Abstract : In an optimizing compiler, the register allocation process is still a crucial phase since it allows to reduce spill code that damages the performances. The register constraints are generally taken into account during the instruction scheduling phase of an acyclic data dependence graph (DAG) : any schedule must minimize the register requirement. However, in a previous work [14], we introduced and mathematically studied the register saturation (RS) concept. It consists of computing the exact upper-bound of the register need for all the valid schedules, independently of the functional unit constraints. The goal of RS is to decouple register constraints from instruction scheduling. 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(n 2) integer variables and O(m + n 2) 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 NPhard. Our detailed experiments in this paper show that our previous heuristics [14] are nearly optimal. We provide a discussion too in order to argument why the RS approach should be better that minimizing the register requirement.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Sid Touati Connect in order to contact the contributor
Submitted on : Friday, February 3, 2012 - 10:50:52 AM
Last modification on : Wednesday, October 20, 2021 - 12:24:14 AM
Long-term archiving on: : Friday, May 4, 2012 - 2:20:17 AM


Files produced by the author(s)




Sid Touati. On the Optimality of Register Saturation. Electronic Notes in Theoretical Computer Science, Elsevier, 2005, 132, pp.131-148. ⟨10.1016/j.entcs.2005.01.033⟩. ⟨hal-00646752⟩



Record views


Files downloads