Introduction : Pourquoi le registre de l'allocation des ressources compte-t-il?

Les processeurs modernes contiennent un petit ensemble de sites de stockage ultra-rapides appelés registres, généralement de 16 à 32 registres à usage général dans des architectures comme x86-64 ou ARM64. Ces registres fonctionnent à la vitesse de l'horloge du processeur, tandis que les accès à la mémoire principale (DRAM) sont des ordres de grandeur plus lents, imposant souvent des centaines de cycles de latence. Une capacité compilateur d'attribuer des variables aux registres au lieu de mémoire détermine directement la vitesse d'exécution, l'efficacité énergétique et la taille du code.

L'attribution des registres, qui permet de déterminer quelles variables résident dans les registres à chaque point du programme, est donc l'une des phases d'optimisation les plus critiques dans tout compilateur. Elle peut faire la différence entre une application louche et une application qui utilise pleinement les capacités du CPU. Parmi les nombreuses techniques inventées pour l'attribution des registres, les algorithmes de coloration des graphiques se sont révélés à la fois élégants et puissants.

Cet article explore la connexion profonde entre la coloration des graphiques et l'attribution des registres. Nous allons parcourir les concepts fondamentaux, l'algorithme classique (algorithme de Chaitin), les techniques avancées comme le regroupement et le déversement, les défis pratiques, et le rôle que joue la coloration des graphiques dans les compilateurs modernes tels que GCC, LLVM, et autres.

Le problème de l'attribution des registres : un regard plus profond

Avant de plonger dans la coloration graphique, il faut définir précisément ce que signifie l'attribution des registres. Une représentation intermédiaire compilatrice (IR) utilise un nombre illimité de registres virtuels – noms qui représentent des variables, des valeurs temporaires et des expressions. La tâche est de mapper ces registres virtuels sur un ensemble fini de registres physiques (la machine cible) afin que deux registres virtuels en direct ne occupent pas simultanément le même registre physique.

Une plage live est l'ensemble des points de programme (entre la définition et la dernière utilisation) où une variable détient une valeur qui sera utilisée plus tard. Deux registres virtuels interfèrent si leurs plages de temps en temps se chevauchent; ils ne peuvent pas partager le même registre physique. L'attribution des registres se réduit ainsi à un problème de coloration graphique[ sur un graphique d'interférence, où les nœuds représentent les registres virtuels et les bords représentent l'interférence. Le nombre de couleurs disponibles équivaut au nombre de registres physiques. Une coloration valide attribue un registre physique (couleur) à chaque noeud de sorte qu'aucun nœud adjacent ne partage la même couleur. Si aucune coloration n'existe pour le nombre donné de registres, certains registres virtuels doivent être spellés à la mémoire, ce qui signifie que leurs valeurs sont stockées sur la pile et rechargées au besoin.

Pourquoi la coloration graphique est-elle un ajustement naturel

La coloration graphique est l'un des problèmes classiques de NP-complet. Pourtant, l'attribution des registres devient NP-complete seulement lorsque nous avons besoin d'une coloration optimale. En pratique, les compilateurs utilisent des algorithmes heuristiques qui produisent de bonnes colorations dans le temps polynôme. La cartographie de l'attribution des registres à la coloration graphique a été décrite pour la première fois par Grégory Chaitin en 1981 dans un papier séminal qui a établi la coloration graphique comme approche dominante.

Construire le graphique d'interférence

La première étape de tout allocateur de couleur graphe consiste à construire un graphique d'interférence à partir de l'information de gamme de programmes en direct. Cela se fait par analyse de variables en direct, une analyse de flux de données classique qui calcule quelles variables sont en direct à chaque point du programme. Une variable est en direct à un point si elle a été définie (une valeur attribuée) et sera lue (utilisée) plus tard sans définition intermédiaire. L'analyse s'effectue généralement sur un graphique de flux de contrôle (CFG) du programme.

Une fois les plages de temps réel connues, on ajoute des bords d'interférence entre deux variables dont les plages de temps réel se chevauchent. Pour l'efficacité, les compilateurs utilisent souvent une représentation plus compacte : une matrice d'interférence [ ou une adjacence bit-vector. Cependant, pour les fonctions très importantes (par exemple, des dizaines de milliers de variables), même la construction du graphique complet peut être coûteuse, et les compilateurs peuvent employer une coalescence itée ou d'autres méthodes progressives pour réduire la taille des graphiques.

Il est important de noter que le graphique d'interférence n'est pas statique dans l'ensemble du programme; il est recalculé par unité ou fonction de compilation. La granularité est importante parce que l'attribution de registre dans une fonction unique (allocation locale) ou mondialement dans une fonction entière utilise les mêmes principes.

L'algorithme de la Chaitin : l'approche classique

L'algorithme Chaitin, nommé d'après Gregory Chaitin, est la base de l'attribution des registres de couleur des graphes. Il fonctionne en plusieurs phases:

  1. Construire: Construire le graphique d'interférence en utilisant une analyse de la distance de vie.
  2. Simplifier: Supprimer à plusieurs reprises les nœuds qui ont moins de voisins K (où K est le nombre de registres physiques) du graphique, les pousser sur une pile. Ces nœuds sont garantis être colorables parce qu'ils ont au plus des voisins K-1 et donc au moins une couleur libre.
  3. Spill: Si aucun noeud avec degré < K existe, sélectionnez un noeud à renverser (c.-à-d., retiré du graphique et stocké en mémoire). Le choix heuristique compte : généralement, les noeuds avec un coût de déversement élevé et/ou un degré élevé sont choisis.
  4. Sélectionner: Pop nœuds de la pile en ordre inverse et leur assigner une couleur (registre physique) non utilisée par un voisin déjà coloré. Si un noeud ne peut pas être attribué (toutes les couleurs K prises par les voisins), il est marqué pour le déversement et l'algorithme doit redémarrer avec le déversement.
  5. Insertion de code de répartition:[ Pour chaque noeud renversé, insérer des instructions de stockage/chargement aux points appropriés pour transférer des valeurs entre la mémoire et les registres. Cela change les plages de temps en temps, de sorte que le processus doit être répété (souvent itératif) jusqu'à ce qu'aucun déversement ne soit nécessaire.

La puissance de l'algorithme de Chaitin="s réside dans sa largeur de registre conservatrice: la phase de simplification assure que les nœuds avec degré < K sont toujours colorables, tandis que le déversement heuristique tente de minimiser les frais généraux d'exécution.

Améliorations : Coloration optimale

L'algorithme original de la Chaitin se déverse de façon prudente : si, à un moment donné, un noeud de sélection ne peut pas être coloré, il se déverse.La coloration optimale modifie cette couleur en supposant que des nœuds à haut degré pourraient encore être colorables plus tard, car certains de leurs voisins pourraient obtenir la même couleur (s'ils n'interfèrent pas entre eux).

Coalcing et partage des tâches

Les allocatateurs de couleur graphique doivent également gérer les copies d'enregistrement à l'enregistrement (déplacement). Lorsqu'une instruction de déplacement copie la valeur d'un registre virtuel à un autre, les deux registres ont des valeurs identiques à ce moment. S'ils ne s'interfèrent pas ailleurs, ils peuvent être rapprochés dans un seul registre virtuel, éliminant le mouvement. Cependant, le regroupement élimine le bord d'interférence entre eux et réduit le nombre de nœuds, aidant à la colorabilité. Le regroupement agressif peut faire demi-tour : il peut augmenter le degré de fusion et causer des déversements.

La séparation de la gamme de vie est une autre technique qui divise une gamme de temps en temps en morceaux plus petits, réduisant les interférences et améliorant souvent la coloration. Elle est particulièrement utile pour l'allocation globale (entre les blocs de base).

Déversements : l'art de choisir ce qu'il faut faire pour être élu

Le déversement est la seule trappe d'évacuation lorsqu'il y a plus de couleurs nécessaires que les registres disponibles. Décider les variables à déverser affecte considérablement les performances. Un heuristique classique est de calculer un coût de transfert [ pour chaque variable, proportionnelle à la pénalité d'exécution estimée de stocker/charger celle-ci. Les coûts peuvent peser plus lourdement les boucles (puisque les déversements à l'intérieur des boucles sont exécutés plusieurs fois).

Après le déversement, le graphique d'interférence change : la variable renversée est supprimée, mais de nouvelles instructions (charges et magasins) introduisent de nouveaux registres virtuels avec de courtes plages de temps. Cette expansion peut nécessiter plusieurs itérations de la boucle d'allocation. En pratique, les compilateurs limitent le nombre d'itérations pour éviter la compilation-décompression, souvent en utilisant un-shot renversant avec un heuristique plus conservateur.

Autres approches pour enregistrer l'attribution

Bien que la coloration des graphiques soit la plus connue, elle n'est pas la seule approche.

  • Linear Scan Allocation:[ Cet algorithme plus simple et plus rapide alloue les registres en balayant l'ordre linéarisé des instructions (par exemple, dans un bloc de base). Il a des frais généraux plus faibles de compilation et fonctionne bien pour les compilateurs juste à temps (JIT) où la vitesse compte. Linear scan[ a été popularisé par le Jikes RVM et est utilisé dans de nombreux JIT (par exemple, le compilateur V8, HotSpot=2].
  • Programmation quadrilatéenne (PBQP) partagée :[ Une méthode plus récente qui formule l'attribution comme un programme quadrilatique, permettant une meilleure gestion des contraintes comme l'aliasage de registre et le parallélisme de niveau d'instruction. PBQP est utilisé dans les LVVM= registre allocator (comme une alternative à l'allocator par défaut avide).
  • Greedy Allocation: La plupart des compilateurs de production modernes (p. ex. GCC, LLVM) utilisent des approches hybrides. LLVM="s allocator par défaut est un "allocator de la grêle qui combine des aspects de la coloration des graphiques et de la numérisation linéaire. Il construit des gammes en direct, assigne des registres virtuels avidement et utilise le fractionnement et l'inflexion (p. ex., les préférences basées sur des instructions de déplacement) pour améliorer la qualité.

Coloration graphique vs. Greedy: compromis pratiques

La coloration graphique pure (style chaitin) fournit un modèle théorique propre mais peut être lente pour de grandes fonctions en raison de la construction graphique et de boucles de déversement répétées. Les allocatateurs modernes échangent souvent l'optimalité pour la vitesse. Par exemple, LLVM="s allocator par défaut n'est pas strictement basé sur la couleur graphique; il utilise un algorithme de division de gamme de vie qui est plus proche de la numérisation linéaire avec rétro-raîchissement. Néanmoins, la perception fondamentale des graphiques d'interférence et de coloration heuristique reste centrale.

Coloration graphique dans les compilateurs du monde réel

Comprendre l'attribution des registres de couleur graphique est essentiel pour les ingénieurs compilateurs travaillant sur tout compilateur sérieux. Voici des exemples de son utilisation:

  • GCC: Le compilateur GCC a utilisé un allocateur de couleur graphe (la phase de «recharger» était l'ancien allocateur). Depuis GCC 4.x, il a été transformé en allocateur de registre régional qui s'appuie sur des principes de couleur graphe mais utilise une heuristique et des fréquences avancées.
  • LLVM: La famille d'allocateurs LLVM=2 comprend une variante de couleur de graphe (l'allocateur de base) et l'allocateur de "greedy" plus avancé. L'allocateur avide construit en interne un graphique d'interférence, mais utilise un schéma fondé sur la priorité pour assigner des registres, ce qui le rapproche de la coloration de graphe en esprit.
  • Java HotSpot Compiler (C2): Le compilateur de serveur utilise un alcoator global de registre de couleur graphique qui gère les registres et les fentes de cheminée. Il effectue la division et le coalcing de gamme en direct, et il est connu pour produire un code hautement optimisé.
  • OpenJDK="s Graal Compiler: Graal utilise un alcoator de registre de couleur de graphe comme une de ses options, en plus d'un balayage linéaire pour les compilations rapides.

Tous ces compilateurs démontrent que la coloration des graphiques n'est pas un exercice académique ; elle affecte directement les performances du logiciel que nous utilisons quotidiennement.

Défis et limites de la coloration des graphiques

Malgré son efficacité, l'attribution des registres de couleurs de graphes est confrontée à des obstacles fondamentaux :

  • NP-Hardness: La coloration optimale est complète. L'heuristique peut produire des colorations sous-optimales, entraînant des déversements inutiles. Pour les fonctions avec de nombreuses plages de temps, l'algorithme peut se battre.
  • Grands graphiques: Les programmes modernes avec l'inline (p. ex., modèles C++) peuvent produire d'énormes fonctions avec des dizaines de milliers de registres virtuels. La construction et la coloration d'un graphique d'interférence complet peuvent devenir prohibitifs. Les compilateurs utilisent souvent allocation en deux phases: allocation locale pour les petits blocs de base et allocation globale pour les sentiers chauds.
  • Complex Hardware Contraintes:[ Les processeurs modernes ont des registres d'alias (par exemple, les demi-registres x86), des paires de registres, des registres à usage spécial (pointeur de pile, registres de drapeau) et des conventions d'appel. La coloration des graphiques doit intégrer ces contraintes, ce qui augmente la complexité du problème de coloration.
  • Précision de la décision de déversement :[ L'heuristique des coûts de déversement repose sur des estimations statiques (p. ex. profondeur de nidification des boucles). L'optimisation guidée par profil peut améliorer cette situation, mais tous les compilateurs n'utilisent pas le profilage.

Stratégies d'atténuation

Les concepteurs de compilateurs ont développé de nombreuses techniques pour relever ces défis. La coloration optimale réduit les insertions de déversement. Le counsivage itéré réduit les déplacements inutiles sans aggraver la colorabilité. La séparation de gamme de vie[ aide les grands graphiques en les brisant en pièces plus petites et colorables. La coloration fondée sur la priorité attribue d'abord des couleurs à des nœuds importants (p. ex., ceux qui ont de nombreuses utilisations en boucles).

Avantages de la coloration graphique: Pourquoi il persiste

Compte tenu de la complexité, pourquoi la coloration des graphiques demeure-t-elle une pierre angulaire?

  • Qualité quasi optimale:[ Pour la plupart des programmes, la coloration des graphiques avec l'heuristique conservatrice produit des affectations de registres au moins aussi bonnes que d'autres méthodes, et souvent meilleures que le balayage linéaire.
  • Fondation théorique claire:[ Le modèle de coloration graphique est élégant et facile à raisonner. Des preuves de justesse (par exemple, la propriété de coloration conservatrice) donnent confiance aux ingénieurs compilateurs.
  • Scalabilité avec l'heuristique: Bien que le comportement le plus défavorable soit pauvre, les programmes du monde réel présentent rarement des graphes d'interférences du pire cas.
  • Extension: De nouvelles fonctionnalités matérielles (p. ex. instructions à registres multiples, contraintes spécifiques à la machine) peuvent être incorporées en ajoutant de nouvelles bordures ou couleurs.

La coloration graphique sert également de base pour évaluer d'autres allocataires. De nombreux articles de recherche comparent leur nouvelle approche à la coloration graphique de style chaitin, démontrant ainsi son importance durable.

Orientations futures : Coloration graphique à l'ère de l'IA et du matériel personnalisé

À mesure que les processeurs évoluent, les unités vectorielles élargies (AVX-512, SVE) et les architectures spécifiques au domaine deviennent encore plus critiques.Les techniques d'apprentissage automatique sont actuellement explorées pour apprendre les décisions de déversement et les heuristiques de coloration.Par exemple, l'apprentissage du renforcement a été appliqué pour enregistrer l'attribution, montrant des promesses dans la réduction des déversements.

De plus, les matériels personnalisés comme les FPGA et les tableaux reconfigurables à grain grossier (CGRA) ont leurs propres contraintes de registre. Les modèles de coloration graphique peuvent être adaptés pour attribuer des unités de calcul ou des tampons. Ceci démontre la polyvalence de l'idée fondamentale : tout problème de planification des ressources avec des restrictions par paires peut être réduit à la coloration graphique.

Conclusion

Les algorithmes de coloration graphique sont plus qu'une simple curiosité académique – ils sont une solution pratique et éprouvée dans le temps à l'un des problèmes d'optimisation les plus importants dans la construction du compilateur. En mapping l'attribution de registre à un problème de coloration graphique, compilateurs peuvent efficacement assigner des registres matériels limités à une abondance de variables de programme, améliorant considérablement la vitesse d'exécution.

Que vous soyez étudiant à l'exploration de la conception du compilateur, un professionnel à l'optimisation d'un compilateur JIT ou un ingénieur travaillant sur le matériel de nouvelle génération, la coloration graphique dans l'attribution des registres fournit un aperçu inestimable de la façon dont logiciel et matériel co-évoluent. L'élégance de colorier un graphique pour rendre les programmes plus rapides continue d'être une histoire fondamentale en informatique – qui combine mathématiques, heuristiques et performance inlassable en génie.