Allocation de registres

Dans un compilateur, l'allocation de registres est une étape importante de la génération de code. Elle vise à choisir dans quel registre du processeur sera rangée chaque variable lors de 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 considérablement plus rapides que celles sur des valeurs en mémoire vive, quand ce ne sont pas les seules possibles. Mais ils sont en nombre très limité, et souvent trop faible pour ranger 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 coloriage de graphe

L'une des méthodes classiques d'allocation de registres consiste à ramener le problème au coloriage 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 peux colorier avec le même registre deux variables qui sont voisines dans le graphe d'interférence. Attribuer k registres aux variables équivaut à colorier avec k couleurs le graphe d'interférences.

Le problème du k-coloriage est NP-complet (pour ) et pour un graphe quelconque. Comme pour n'importe quel graphe G il est possible de créer un programme dont le graphe d'interférences est G, 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 à colorier : on cherche dans le graphe un sommet de degré strictement inférieur à k. On est certain de pouvoir colorier ce sommet puisque ses voisins utiliseront au plus k − 1 couleurs. Ainsi on le supprime du graphe et on le garde de côté. Si on arrive à colorier récursivement le graphe simplifié, alors on pourra le réinsérer et le colorier.

Si tous les sommets ont au moins pour degré k, plusieurs stratégies sont possibles :

• On peut continuer le coloriage 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 colorier à la remontée. Lors de la remontée, on attribue alors à chaque sommet rencontré la première couleur disponible, quitte à dépasser k, 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.

Voir aussi

• Recherche de sous-expressions communes

• Portail de l’informatique