Allocation de registres
Dans un compilateur, l'allocation de registres est une étape importante de la génération de code. Elle vise à choisir judicieusement dans quel registre du processeur seront enregistrées les variables durant l'exécution du programme que l'on compile.
Les registres sont des mémoires internes au processeur, généralement capables de contenir un mot machine. Les opérations sur des valeurs rangées dans des registres sont plus rapides que celles sur des valeurs en mémoire vive, quand ce ne sont pas les seules possibles. Mais un processeur compte rarement plus de quelques dizaines de registres, bien trop peu pour toutes les variables d'un programme. Il est donc crucial de choisir avec pertinence les variables qui doivent résider dans les registres à chaque étape de l'exécution. Cela étant difficile dans les premières étapes de la compilation, on commence par faire comme si l'on disposait d'un nombre illimité de registres, puis l'on attribue à ces registres virtuels des registres réels ou des emplacements en mémoire.
Allocation de registres par coloration de graphe
L'une des méthodes classiques d'allocation de registres consiste à ramener le problème à la coloration du graphe d'interférence des variables. Les sommets de ce graphe sont les variables du programme, et deux sommets sont reliés par une arête si les variables correspondantes interfèrent.
On dit que deux variables interfèrent lorsque l'une est définie pendant que l'autre est active (c'est-à-dire susceptible d'être utilisée dans la suite de l'exécution). Deux variables qui interfèrent ne peuvent pas être placées dans le même registre — à une nuance technique près : sur certains processeurs, les registres ne sont pas équivalents. On étend donc aux registres la relation d'interférence, en convenant qu'ils interfèrent tous entre eux, et qu'une variable interfère avec les registres qui lui sont interdits. Ainsi, on ne peut colorer avec le même registre deux variables qui sont voisines dans le graphe d'interférence. Attribuer registres aux variables équivaut à colorer avec couleurs le graphe d'interférences.
Le problème de la -coloration est NP-complet (pour ) et pour un graphe quelconque. Comme pour n'importe quel graphe il est possible de créer un programme dont le graphe d'interférences est , le problème d'allocation de registres est aussi NP-complet. Aussi on utilise en général une heuristique qui fournit de bons résultats pratiques. Elle consiste à supprimer du graphe les sommets faciles à colorer : on cherche dans le graphe un sommet de degré strictement inférieur à . On est certain de pouvoir colorer ce sommet puisque ses voisins utiliseront au plus couleurs. Ainsi on le supprime du graphe et on le garde de côté. Si on arrive à colorer récursivement le graphe simplifié, alors on pourra le réinsérer et le colorer.
Si tous les sommets ont au moins pour degré , plusieurs stratégies sont possibles :
- on peut continuer la coloration et retirer à chaque étape un sommet de degré minimal, en espérant que deux de ses voisins auront la même couleur, de sorte que l'on parviendra à le colorer à la remontée. Lors de la remontée, on attribue alors à chaque sommet rencontré la première couleur disponible, quitte à dépasser , puis on évalue le coût de rangement en mémoire des variables de chaque couleur, pour affecter à chacune un registre réel ou une case mémoire. Il est possible de faire un peu mieux, en essayant de choisir pour chaque sommet une couleur parmi celles des voisins de ses voisins ;
- une autre méthode consiste à sélectionner, au contraire, un sommet de degré maximal, dans l'espoir que sa suppression simplifiera considérablement le graphe. Si l'on dispose d'informations sur le coût de mise en mémoire, un meilleur indicateur est le quotient du coût de mise en pile par le degré. Les systèmes d'allocation de registres réels utilisent des heuristiques un peu plus perfectionnées, qui peuvent combiner ces deux méthodes. Notons enfin qu'il est parfois moins coûteux de recalculer une valeur (si les opérandes résident dans des registres, par exemple) que de l'enregistrer pour la relire.
