Allocation de registres

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 k \geq 3) 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



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Allocation de registres de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Allocation De Registres — Dans un compilateur, l allocation de registres est une étape importante de la production 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… …   Wikipédia en Français

  • allocation — [ alɔkasjɔ̃ ] n. f. • 1516; allocacion « inscription, enregistrement » 1478; lat. médiév. allocatio → allouer ♦ Fait d allouer; somme allouée, prestation en argent. Voyageur qui demande une allocation de devises. Spécialt Prestation en argent… …   Encyclopédie Universelle

  • Génération de code natif — La génération de code natif est l étape du processus de compilation transformant l arbre syntaxique abstrait enrichi d informations sémantiques en code machine ou en bytecode spécialisé pour la plateforme cible. C est l avant dernière étape du… …   Wikipédia en Français

  • Déplacement des invariants de boucle — En programmation informatique, les invariants de boucle sont des instructions ou des expressions d un langage de programmation impératif qui peut être déplacé hors du corps de la boucle sans affecter le résultat du programme. Le déplacement des… …   Wikipédia en Français

  • Compilateur — Pour les articles homonymes, voir Compilation. Un compilateur est un programme informatique qui traduit un langage (appelé le langage source) en un autre (le langage cible), généralement dans le but de créer un exécutable. Un compilateur sert le… …   Wikipédia en Français

  • Compilateur croisé — Compilateur Pour les articles homonymes, voir Compilation. Un compilateur est un programme informatique qui traduit un langage, le langage source, en un autre, appelé le langage cible, en préservant la signification du texte source. Ce schéma… …   Wikipédia en Français

  • Compilation (informatique) — Compilateur Pour les articles homonymes, voir Compilation. Un compilateur est un programme informatique qui traduit un langage, le langage source, en un autre, appelé le langage cible, en préservant la signification du texte source. Ce schéma… …   Wikipédia en Français

  • Compilation croisée — Compilateur Pour les articles homonymes, voir Compilation. Un compilateur est un programme informatique qui traduit un langage, le langage source, en un autre, appelé le langage cible, en préservant la signification du texte source. Ce schéma… …   Wikipédia en Français

  • Compilo — Compilateur Pour les articles homonymes, voir Compilation. Un compilateur est un programme informatique qui traduit un langage, le langage source, en un autre, appelé le langage cible, en préservant la signification du texte source. Ce schéma… …   Wikipédia en Français

  • LLVM — Low Level Virtual Machine Low Level Virtual Machine Développeur LLVM Developer Group Dernièr …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”