Attribution des registres

Dans l'optimisation du compilateur , l'allocation de registres est le processus d'attribution de variables automatiques locales et de résultats d'expression à un nombre limité de registres du processeur .

L'allocation de registre peut se faire sur un bloc de base ( allocation de registre local ), sur une fonction/ procédure entière ( allocation de registre global ) ou au-delà des limites de fonction traversées via un graphe d'appel ( allocation de registre interprocédural ). Lorsqu'elle est effectuée par fonction/procédure, la convention d'appel peut nécessiter l'insertion d'une sauvegarde/restauration autour de chaque site d'appel .

Dans de nombreux langages de programmation , le programmeur peut utiliser n'importe quel nombre de variables . L'ordinateur peut lire et écrire rapidement des registres dans le processeur , de sorte que le programme informatique s'exécute plus rapidement lorsque davantage de variables peuvent se trouver dans les registres du processeur. De plus, le code accédant aux registres est parfois plus compact, de sorte que le code est plus petit et peut être récupéré plus rapidement s'il utilise des registres plutôt que de la mémoire. Cependant, le nombre de registres est limité. Par conséquent, lorsque le compilateur traduit le code en langage machine, il doit décider comment allouer des variables au nombre limité de registres dans le processeur.

Toutes les variables ne sont pas utilisées (ou « actives ») en même temps, donc, au cours de la vie d'un programme, un registre donné peut être utilisé pour contenir différentes variables. Cependant, deux variables utilisées en même temps ne peuvent pas être affectées au même registre sans corrompre l'une des variables. S'il n'y a pas assez de registres pour contenir toutes les variables, certaines variables peuvent être déplacées vers et depuis la RAM . Ce processus est appelé « déversement » des registres. Au cours de la vie d'un programme, une variable peut être à la fois déversée et stockée dans des registres : cette variable est alors considérée comme « divisée ». L'accès à la RAM est nettement plus lent que l'accès aux registres et donc un programme compilé s'exécute plus lentement. Par conséquent, un compilateur optimisant vise à affecter autant de variables que possible aux registres. Une « pression de registre » élevée est un terme technique qui signifie que davantage de déversements et de rechargements sont nécessaires ; elle est définie par Braun et al. comme « le nombre de variables actives simultanément dans une instruction ».

De plus, certains ordinateurs conçoivent des caches de registres fréquemment consultés. Ainsi, les programmes peuvent être optimisés davantage en affectant le même registre à une source et à une destination d'une moveinstruction chaque fois que cela est possible. Ceci est particulièrement important si le compilateur utilise une représentation intermédiaire telle que la forme statique à affectation unique (SSA). En particulier, lorsque la SSA n'est pas entièrement optimisée, elle peut générer artificiellement des instructions supplémentaires move.

L'allocation de registres consiste donc à choisir où stocker les variables lors de l'exécution, c'est-à-dire à l'intérieur ou à l'extérieur des registres. Si la variable doit être stockée dans des registres, l'allocateur doit alors déterminer dans quel(s) registre(s) cette variable sera stockée. Enfin, un autre défi consiste à déterminer la durée pendant laquelle une variable doit rester au même endroit.

Un répartiteur de registres, quelle que soit la stratégie d'allocation choisie, peut s'appuyer sur un ensemble d'actions de base pour relever ces défis. Ces actions peuvent être regroupées dans plusieurs catégories différentes :

Déplacer l'insertion

Cette action consiste à augmenter le nombre d'instructions de déplacement entre les registres, c'est-à-dire à faire vivre une variable dans différents registres au cours de sa durée de vie, au lieu d'un seul. Cela se produit dans l'approche de plage de durée de vie divisée.

Effusion

Cette action consiste à stocker une variable en mémoire au lieu de registres.

Affectation

Cette action consiste à affecter un registre à une variable.

Coalescence

Cette action consiste à limiter le nombre de déplacements entre les registres, limitant ainsi le nombre total d'instructions. Par exemple, en identifiant une variable active dans différentes méthodes et en la stockant dans un registre pendant toute sa durée de vie.

De nombreuses approches d’allocation de registre optimisent une ou plusieurs catégories spécifiques d’actions.

L'allocation des registres soulève plusieurs problèmes qui peuvent être résolus (ou évités) par différentes approches d'allocation des registres. Trois des problèmes les plus courants sont identifiés comme suit :

Aliasing

Dans certaines architectures, l'attribution d'une valeur à un registre peut affecter la valeur d'un autre : c'est ce qu'on appelle l'aliasing. Par exemple, l' architecture x86 possède quatre registres 32 bits à usage général qui peuvent également être utilisés comme registres 16 bits ou 8 bits. Dans ce cas, l'attribution d'une valeur 32 bits au registre eax affectera la valeur du registre al.

Pré-coloration

Ce problème consiste à forcer l'affectation de certaines variables à des registres particuliers. Par exemple, dans les conventions d'appel PowerPC , les paramètres sont généralement transmis dans R3-R10 et la valeur de retour est transmise dans R3.

Problème NP

Chaitin et al. ont montré que l'allocation de registres est un problème NP-complet . Ils réduisent le problème de coloration de graphe au problème d'allocation de registres en montrant que pour un graphe arbitraire, un programme peut être construit de telle sorte que l'allocation de registres pour le programme (avec des registres représentant des nœuds et des registres de machines représentant des couleurs disponibles) soit une coloration pour le graphe d'origine. Comme la coloration de graphe est un problème NP-difficile et que l'allocation de registres est en NP, cela prouve la complétude NP du problème.

L'allocation de registres peut se faire sur un bloc de code de base : on dit qu'elle est « locale », et elle a été mentionnée pour la première fois par Horwitz et al. Comme les blocs de base ne contiennent pas de branches, le processus d'allocation est considéré comme rapide, car la gestion des points de fusion du graphe de contrôle de flux dans l'allocation de registres se révèle être une opération qui prend du temps Cependant, on pense que cette approche ne produit pas un code aussi optimisé que l'approche « globale », qui opère sur l'ensemble de l'unité de compilation (une méthode ou une procédure par exemple).

L'allocation par coloration de graphe est l'approche prédominante pour résoudre l'allocation de registre. Elle a été proposée pour la première fois par Chaitin et al. Dans cette approche, les nœuds du graphe représentent des plages actives ( variables , temporaires , registres virtuels/symboliques) qui sont candidates à l'allocation de registre. Les arêtes connectent les plages actives qui interfèrent, c'est-à-dire les plages actives qui sont simultanément actives à au moins un point du programme. L'allocation de registre se réduit alors au problème de coloration de graphe dans lequel des couleurs (registres) sont attribuées aux nœuds de telle sorte que deux nœuds connectés par une arête ne reçoivent pas la même couleur.

En utilisant l'analyse de vivacité , un graphique d'interférence peut être construit. Le graphique d'interférence, qui est un graphique non orienté où les nœuds sont les variables du programme, est utilisé pour modéliser les variables qui ne peuvent pas être attribuées au même registre.

Les principales phases d'un allocateur de registres à coloration graphique de style Chaitin sont :

1. Renuméroter : découvrez les informations de portée en direct dans le programme source.
2. Construire : construire le graphe d'interférence.
3. Coalesce : fusionner les plages actives de variables non interférentes liées par des instructions de copie.
4. Coût de déversement : calculez le coût de déversement de chaque variable. Cela permet d'évaluer l'impact du mappage d'une variable en mémoire sur la vitesse du programme final.
5. Simplifier : construire un ordre des nœuds dans le graphe d'inférences
6. Code de déversement : insérez des instructions de déversement, c'est-à-dire chargez et stockez pour commuter les valeurs entre les registres et la mémoire.
7. Sélectionner : attribuer un registre à chaque variable.

L'allocation par coloration de graphe présente trois inconvénients majeurs. Tout d'abord, elle repose sur la coloration de graphe, qui est un problème NP-complet , pour décider quelles variables sont déversées. Trouver un graphe de coloration minimal est en effet un problème NP-complet. Deuxièmement, à moins que le fractionnement de plage en direct ne soit utilisé, les variables évincées sont déversées partout : les instructions de stockage sont insérées le plus tôt possible, c'est-à-dire juste après les définitions de variables ; les instructions de chargement sont respectivement insérées tard, juste avant l'utilisation des variables. Troisièmement, une variable qui n'est pas déversée est conservée dans le même registre pendant toute sa durée de vie.

D'autre part, un nom de registre unique peut apparaître dans plusieurs classes de registres, où une classe est un ensemble de noms de registres interchangeables dans un rôle particulier. Ensuite, plusieurs noms de registres peuvent être des alias pour un seul registre matériel. Enfin, la coloration graphique est une technique agressive pour l'allocation de registres, mais elle est coûteuse en calcul en raison de son utilisation du graphique d'interférence, qui peut avoir une taille de cas extrême qui est quadratique dans le nombre de plages actives. La formulation traditionnelle de l'allocation de registres par coloration graphique suppose implicitement une seule banque de registres à usage général non chevauchants et ne gère pas les caractéristiques architecturales irrégulières telles que les paires de registres qui se chevauchent, les registres à usage spécial et les banques de registres multiples.

Une amélioration ultérieure de l'approche de coloration graphique de style Chaitin a été trouvée par Briggs et al. : elle est appelée coalescence conservatrice. Cette amélioration ajoute un critère pour décider quand deux plages actives peuvent être fusionnées. Principalement, en plus des exigences de non-interférence, deux variables ne peuvent être fusionnées que si leur fusion ne provoque pas de débordement supplémentaire. Briggs et al. introduisent une deuxième amélioration aux travaux de Chaitin qui est la coloration biaisée. La coloration biaisée essaie d'attribuer la même couleur dans la coloration graphique aux plages actives qui sont liées à la copie.

L'analyse linéaire est une autre approche d'allocation de registre global. Elle a été proposée pour la première fois par Poletto et al. en 1999. Dans cette approche, le code n'est pas transformé en graphique. Au lieu de cela, toutes les variables sont analysées linéairement pour déterminer leur plage de vie, représentée sous forme d'intervalle. Une fois que les plages de vie de toutes les variables ont été déterminées, les intervalles sont parcourus chronologiquement. Bien que cette traversée puisse aider à identifier les variables dont les plages de vie interfèrent, aucun graphique d'interférence n'est construit et les variables sont allouées de manière gourmande.

La motivation de cette approche est la rapidité ; non pas en termes de temps d'exécution du code généré, mais en termes de temps passé à la génération de code. En général, les approches de coloration de graphes standard produisent du code de qualité, mais ont une surcharge importante , l'algorithme de coloration de graphes utilisé ayant un coût quadratique. En raison de cette fonctionnalité, l'analyse linéaire est l'approche actuellement utilisée dans plusieurs compilateurs JIT, comme le compilateur client Hotspot , V8 , Jikes RVM , et Android Runtime (ART). Le compilateur serveur Hotspot utilise la coloration de graphes pour son code supérieur.

Ceci décrit l'algorithme tel que proposé pour la première fois par Poletto et al., où :

• R est le nombre de registres disponibles.
• active est la liste, triée par ordre croissant de point final, des intervalles en direct chevauchant le point actuel et placés dans des registres.

Allocation de registre de balayage linéaire actif ← {} pour chaque intervalle en direct i , par ordre croissant de point de départ, faites ExpireOldIntervals(i) si longueur(active) = R alors Déversement à intervalle (i) autre registre[i] ← un registre supprimé du pool de registres libres ajouter i à actif, trié par point final croissant ExpireOldIntervals(i) 
pour chaque intervalle j 
dans actif, par ordre croissant de point final, faire 
si endpoint[j] ≥ startpoint[i] alors 
renvoyer supprimer j de actif ajouter le registre [j] au pool de registres libres Déversement à intervalle (i) déversement ← dernier intervalle en actif si endpoint[spill] > endpoint[i] alors registre[i] ← registre[déversement] emplacement [déversement] ← nouvel emplacement de la pile éliminer le déversement de l'actif ajouter i à actif, trié par point final croissant sinon emplacement[i] ← nouvel emplacement de la pile 

Cependant, le scan linéaire présente deux inconvénients majeurs. D'abord, en raison de son aspect gourmand, il ne prend pas en compte les trous de durée de vie, c'est-à-dire les « plages où la valeur de la variable n'est pas nécessaire ». De plus, une variable renversée restera renversée pendant toute sa durée de vie.

De nombreux autres travaux de recherche ont suivi l'algorithme de balayage linéaire de Poletto. Traub et al., par exemple, ont proposé un algorithme appelé binpacking de seconde chance visant à générer du code de meilleure qualité. Dans cette approche, les variables déversées ont la possibilité d'être stockées ultérieurement dans un registre en utilisant une heuristique différente de celle utilisée dans l'algorithme de balayage linéaire standard. Au lieu d'utiliser des intervalles en direct, l'algorithme s'appuie sur des plages en direct, ce qui signifie que si une plage doit être déversée, il n'est pas nécessaire de déverser toutes les autres plages correspondant à cette variable.

L'allocation linéaire par balayage a également été adaptée pour tirer parti de la forme SSA : les propriétés de cette représentation intermédiaire simplifient l'algorithme d'allocation et permettent de calculer directement les trous de durée de vie. Tout d'abord, le temps passé dans l'analyse des graphes de flux de données, visant à construire les intervalles de durée de vie, est réduit, notamment parce que les variables sont uniques. Elle produit par conséquent des intervalles de vie plus courts, car chaque nouvelle affectation correspond à un nouvel intervalle de vie. Pour éviter de modéliser les intervalles et les trous de vie, Rogers a montré une simplification appelée ensembles futurs actifs qui a réussi à supprimer les intervalles pour 80 % des instructions.

Dans le contexte de l'allocation de registres, la fusion est l'acte de fusionner des opérations de déplacement de variable à variable en allouant ces deux variables au même emplacement. L'opération de fusion a lieu après la construction du graphique d'interférence. Une fois que deux nœuds ont été fusionnés, ils doivent obtenir la même couleur et être alloués au même registre, une fois que l'opération de copie devient inutile.

La coalescence peut avoir des impacts positifs et négatifs sur la colorabilité du graphe d'interférence. Par exemple, un impact négatif que la coalescence pourrait avoir sur la colorabilité de l'inférence du graphe est lorsque deux nœuds sont coalescés, car le nœud résultant aura une union des arêtes de ceux qui sont coalescés. Un impact positif de la coalescence sur la colorabilité du graphe d'inférence est, par exemple, lorsqu'un nœud interfère avec les deux nœuds en cours de coalescence, le degré du nœud est réduit d'un, ce qui conduit à améliorer la colorabilité globale du graphe d'interférence.

Il existe plusieurs heuristiques de coalescence disponibles :

Coalescence agressive

il a été introduit pour la première fois par l'allocateur de registre original de Chaitin. Cette heuristique vise à fusionner tous les nœuds non interférents liés à la copie. Du point de vue de l'élimination de la copie, cette heuristique donne les meilleurs résultats. D'un autre côté, une fusion agressive pourrait avoir un impact sur la colorabilité du graphe d'inférence.

Coalition conservatrice

il utilise principalement la même heuristique que la coalescence agressive mais il fusionne les mouvements si, et seulement si, cela ne compromet pas la colorabilité du graphe d'interférence.

Coalescence itérée

il supprime un mouvement particulier à la fois, tout en conservant la colorabilité du graphique.

Une fusion optimiste

il est basé sur une coalescence agressive, mais si la colorabilité du graphe d'inférence est compromise, il abandonne le moins de mouvements possible.

D'autres approches d'allocation de registres ne se limitent pas à une seule technique pour optimiser l'utilisation du registre. Cavazos et al., par exemple, ont proposé une solution où il est possible d'utiliser à la fois l'analyse linéaire et les algorithmes de coloration de graphes. Dans cette approche, le choix entre l'une ou l'autre solution est déterminé de manière dynamique : tout d'abord, un algorithme d'apprentissage automatique est utilisé « hors ligne », c'est-à-dire pas au moment de l'exécution, pour construire une fonction heuristique qui détermine quel algorithme d'allocation doit être utilisé. La fonction heuristique est ensuite utilisée au moment de l'exécution ; à la lumière du comportement du code, l'allocateur peut alors choisir entre l'un des deux algorithmes disponibles.

L'allocation de registres de traces est une approche récente développée par Eisl et al. Cette technique gère l'allocation localement : elle s'appuie sur des données de profilage dynamique pour déterminer quelles branches seront les plus fréquemment utilisées dans un graphe de flux de contrôle donné. Elle en déduit ensuite un ensemble de « traces » (c'est-à-dire des segments de code) dans lesquelles le point de fusion est ignoré au profit de la branche la plus utilisée. Chaque trace est ensuite traitée indépendamment par l'allocateur. Cette approche peut être considérée comme hybride car il est possible d'utiliser différents algorithmes d'allocation de registres entre les différentes traces.

L'allocation fractionnée est une autre technique d'allocation de registres qui combine différentes approches, généralement considérées comme opposées. Par exemple, la technique d'allocation hybride peut être considérée comme fractionnée car la première étape de construction heuristique est effectuée hors ligne et l'utilisation heuristique est effectuée en ligne. De la même manière, B. Diouf et al. ont proposé une technique d'allocation reposant à la fois sur des comportements hors ligne et en ligne, à savoir la compilation statique et dynamique. Au cours de l'étape hors ligne, un ensemble de déversement optimal est d'abord collecté à l'aide de la programmation linéaire en nombres entiers . Ensuite, les plages en direct sont annotées à l'aide de l' compressAnnotationalgorithme qui s'appuie sur l'ensemble de déversement optimal précédemment identifié. L'allocation de registres est effectuée ensuite pendant l'étape en ligne, sur la base des données collectées dans la phase hors ligne.

En 2007, Bouchez et al. ont également suggéré de diviser l'allocation des registres en différentes étapes, une étape étant dédiée au déversement et une autre à la coloration et à la coalescence.

Plusieurs mesures ont été utilisées pour évaluer les performances d'une technique d'allocation de registres par rapport à une autre. L'allocation de registres doit généralement faire face à un compromis entre la qualité du code, c'est-à-dire un code qui s'exécute rapidement, et la surcharge d'analyse, c'est-à-dire le temps passé à déterminer l'analyse du code source pour générer du code avec une allocation de registres optimisée. De ce point de vue, le temps d'exécution du code généré et le temps passé à l'analyse de la vivacité sont des mesures pertinentes pour comparer les différentes techniques.

Une fois les mesures pertinentes choisies, le code sur lequel les mesures seront appliquées doit être disponible et pertinent pour le problème, soit en reflétant le comportement d'une application réelle, soit en étant pertinent pour le problème particulier que l'algorithme souhaite résoudre. Les articles les plus récents sur l'allocation de registres utilisent notamment la suite de tests Dacapo.