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.
Type de document :
Article dans une revue
Electronic Notes in Theoretical Computer Science, Elsevier, 2005, 132, pp.131-148. 〈10.1016/j.entcs.2005.01.033〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00646752
Contributeur : Sid Touati <>
Soumis le : vendredi 3 février 2012 - 10:50:52
Dernière modification le : jeudi 11 janvier 2018 - 06:21:30
Document(s) archivé(s) le : vendredi 4 mai 2012 - 02:20:17

Fichier

ENTCS643.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

160

Téléchargements de fichiers

73