🧠Allocateur de registres: méthode, résultats & 2026
Découvrez comment l’allocateur de registres optimise l’allocation de registres : moins de code généré, compilation plus rapide grâce aux intervalles de vie. Méthode 2026.
Simplifier un allocateur de registres sans dégrader le code
Un allocateur de registres décide où conserver les valeurs manipulées par un programme pendant son exécution. Il peut les placer dans les registres du processeur, rapides mais limités, ou en mémoire, ce qui demande davantage d'instructions. Ce n'est pas une « grosse » étape en surface, mais ses choix se voient directement dans le code généré et dans le temps de compilation.
Le retour d'expérience présenté ici part d'un cas assez concret : un allocateur par parcours linéaire fonctionnait, mais son implémentation s'est alourdie au fil des correctifs jusqu'à dépasser 1 300 lignes. L'auteur a mesuré l'impact de ses fonctionnalités, puis l'a remplacé par un allocateur à priorité. L'idée était simple : traiter d'abord les intervalles de vie les plus utiles et leur attribuer le premier registre compatible.
Le résultat est plus petit, plus rapide à exécuter et produit moins d'instructions. Et pourtant, on ne retrouve ni éviction des valeurs déjà placées, ni découpage des intervalles, ni seconde passe. Voilà comment l'approche fonctionne, ce qu'elle améliore, et ce qu'elle choisit de laisser de côté.
Pourquoi l'allocation de registres est un problème difficile
Un compilateur commence souvent par utiliser des registres virtuels, en nombre pratiquement illimité. Le processeur, lui, n'en propose qu'un nombre fini. L'allocateur doit donc associer chaque registre virtuel à un registre physique, ou lui réserver un emplacement sur la pile quand les registres disponibles ne suffisent pas.
Le critère central, c'est la durée de vie d'une valeur : elle démarre quand la valeur est produite et se termine à sa dernière lecture. Si deux valeurs se chevauchent dans le temps, elles ne peuvent pas partager le même registre. Quand trop de valeurs sont « vivantes » en même temps, certaines finissent en mémoire : c'est ce qu'on appelle un spill. En pratique, cela implique souvent un stockage puis un rechargement.
L'objectif ne se limite donc pas à « mettre des valeurs dans des registres ». Il faut aussi décider lesquelles garder, lesquelles déborder en pile, et comment éviter les copies inutiles. Trouver l'affectation optimale est un problème difficile : l'allocation générale ressemble au coloriage de graphes, et les allocateurs réels s'appuient donc sur des heuristiques.
La convention d'appel réduit les choix disponibles
Les appels de fonctions ajoutent des contraintes. Avec la convention d'appel x86-64 utilisée sous Linux, certains registres sont caller-saved : un appel peut les modifier. Donc si une valeur doit survivre à l'appel, elle ne peut pas rester dans un de ces registres sans être sauvegardée ailleurs. Les registres callee-saved, au contraire, doivent être restaurés par la fonction qui les utilise.
Prenons une fonction qui appelle g(x), puis additionne le résultat à y. La valeur y reste vivante pendant l'appel. Un allocateur qui place y dans un registre caller-saved doit gérer une sauvegarde/restauration, ou déplacer la valeur. Un allocateur qui choisit un registre callee-saved peut conserver y pendant l'appel, mais il paie le prix dans le prologue et l'épilogue.
Dans l'exemple étudié, le compilateur choisit rbx pour garder y. Le résultat de l'appel reste dans rax, et l'addition se fait directement entre rax et rbx. Ce détail compte : l'allocateur n'a pas une règle « toute valeur vivante à travers un appel va dans un callee-saved ». Le choix émerge des contraintes liées aux positions où les registres caller-saved sont déjà pris.
En pratique, ça simplifie le raisonnement : plutôt que d'accumuler des exceptions, un modèle local des contraintes suffit à produire un comportement utile.
Les cinq Ă©tapes de l'allocateur
L'allocateur étudié suit cinq étapes, pour chaque fonction :
- Calculer les intervalles de vie des registres virtuels.
- Marquer les registres physiques réservés par les instructions et la convention d'appel.
- Coalescer les copies pour que certaines valeurs partagent un registre.
- Attribuer les registres, en commençant par les valeurs prioritaires.
- Déborder les valeurs restantes sur la pile, puis réécrire les instructions.
La simplicité ne vient pas seulement de ce qu'il fait, mais aussi de ce qu'il évite. Une fois qu'un bundle obtient un registre, l'allocateur ne le reprend pas pour le donner à une autre valeur. Il ne découpe pas non plus une durée de vie en deux morceaux « parce que ça arrange ». Et surtout, il ne relance pas le processus une seconde fois après un échec.
On trouve ces mécanismes dans des allocateurs plus élaborés (récupération de registres, améliorations locales, etc.). Ils peuvent aider, mais ils augmentent aussi le nombre de cas à gérer et le coût d'implémentation. La vraie question, c'est : est-ce que ça améliore suffisamment le code réel pour mériter la complexité ?
Donner des positions précises aux instructions
Pour comparer les intervalles, chaque instruction reçoit deux positions, ou slots : une position de lecture et une position d'écriture. Une valeur source peut se terminer à sa lecture si l'instruction est une copie. La valeur destination commence à l'écriture. Les deux intervalles ne se chevauchent pas : ils peuvent partager le même registre, et la copie devient inutile.
Pour les autres instructions, les sources restent vivantes jusqu'à l'écriture du résultat. Ça évite qu'un résultat écrase un opérande qui doit encore être lu au moment de l'instruction. Sur x86, c'est particulièrement important, parce que certaines opérations modifient le premier opérande (par exemple add). Le compilateur peut donc avoir besoin d'une copie préalable, et c'est l'étape de coalescence qui essaie de la supprimer si les durées de vie le permettent.
Repérer les intervalles discontinus
Une durée de vie n'est pas toujours continue. Une valeur peut être ignorée dans une partie du programme, puis réutilisée plus loin. Ces « trous » forment des zones mortes dans l'intervalle.
L'organisation des blocs dans le code machine peut rendre ces trous utiles. Dans une boucle, par exemple, le bloc de sortie se place entre des blocs de boucle. Une valeur temporaire utilisée pour calculer une adresse n'est plus nécessaire dans le bloc de sortie : le registre qui la contenait peut alors servir pour le résultat final. Conserver les trous évite de marquer le registre comme occupé « partout » entre la première définition et la dernière utilisation.
Priorité, coalescence et débordement en mémoire
Avant d'affecter les registres, l'allocateur essaie de supprimer des copies. Deux registres virtuels reliés par une copie peuvent partager un registre si leurs intervalles ne se chevauchent pas et s'ils appartiennent à la même classe de registres. Le groupe obtenu, appelé bundle, porte les segments fusionnés et le poids total. Ensuite, les copies internes au bundle peuvent être supprimées.
Les copies issues d'instructions à deux opérandes ou de nœuds phi sont des candidates classiques. Les copies vers un registre physique ne fusionnent pas forcément les valeurs : elles expriment plutôt une préférence. Si le registre est libre, le bundle peut l'obtenir, et la copie disparaît à l'allocation.
L'examen des copies se fait avec une priorité sur les copies situées dans les boucles les plus profondes. Une copie « chaude » a plus de chances d'être supprimée avant qu'une fusion ultérieure ne rende l'opération impossible. Pour gérer ces bundles, l'implémentation utilise une structure union-find afin de suivre efficacement les fusions. Et pour éviter que la fusion de plages trop fragmentées ne devienne coûteuse, elle renonce à certaines fusions au-delà d'un seuil de segments.
Attribuer les registres aux valeurs les plus importantes
Chaque bundle reçoit une priorité calculée à partir de son poids et de la longueur de ses intervalles :
priorité = poids / racine carrée de la longueur en slots
Les plages courtes et « chaudes » passent souvent en premier : elles ont un poids élevé et s'insèrent généralement plus facilement. Les plages longues et rarement utilisées viennent plus tard et risquent davantage d'être envoyées sur la pile. La racine carrée adoucit toutefois la pénalisation d'une valeur longue (par exemple un compteur de boucle).
Pour chaque bundle, l'allocateur collecte d'abord les registres déjà bloqués sur ses segments. Il choisit d'abord son registre préféré s'il est libre, puis parcourt l'ordre de priorité de sa classe de registres. Dans cet ordre, les registres caller-saved sont essayés avant les callee-saved.
Dans l'exemple où y survit à un appel, les contraintes associées à x et au résultat favorisent respectivement rdi et rax. Comme tous les caller-saved sont déjà pris au moment de l'appel, y finit sur rbx. La fonction n'a alors qu'à sauvegarder/restaurer les callee-saved qu'elle utilise réellement.
Il y a une limite qui dépend de la plateforme : sous Linux, les registres XMM sont caller-saved dans la convention d'appel. Donc une valeur flottante qui doit survivre à un appel ne peut pas rester dans un XMM callee-saved ; elle doit être déplacée, typiquement sur la pile. Les conventions d'appel changent selon les systèmes : il faut adapter ces règles à la cible, plutôt que généraliser un résultat observé sur Linux à Windows.
Déborder une valeur et réécrire le code
Quand aucun registre ne convient, le bundle est placé sur la pile pour toute sa durée de vie. Les bundles débordés sont triés par début d'intervalle, et un emplacement de pile peut être réutilisé dès qu'une valeur précédente n'est plus vivante.
La réécriture convertit ensuite les registres virtuels en registres physiques. Pour un opérande débordé, l'allocateur insère un chargement vers un registre temporaire avant l'instruction ; pour un résultat débordé, il ajoute un stockage après. Il utilise en priorité des registres temporaires dédiés. S'ils sont occupés, il cherche un autre registre libre à ce point.
Certaines copies se transforment directement en chargement ou en stockage : pas besoin d'un temporaire dans ces cas. De même, un argument passé sur la pile peut parfois être lu directement depuis son emplacement.
La première version du code n'est pas forcément minimale. Un passage peephole ultérieur peut supprimer un rechargement si le registre temporaire n'a pas été modifié entre le stockage et la lecture. Et si plus rien ne lit l'emplacement correspondant, le stockage devient lui aussi inutile. C'est un compromis : l'allocateur reste simple, et une optimisation locale retire les redondances faciles à détecter.
Résultats, limites et fonctionnalités supprimées
Par rapport à l'ancien allocateur par parcours linéaire, le nouvel allocateur réduit son propre code source de 58 %. Sur les tests mentionnés, le nombre d'instructions générées baisse de 3,6 % et celui des stockages de 22 %. Pour la compilation de SQLite avec -O0, le temps passé dans l'allocateur diminue de 77 %, tandis que le temps total de compilation baisse de 43 %.
Ces chiffres sont parlants, mais leur portée compte. Ils décrivent un compilateur, un ensemble de mesures précis, et ils ne prouvent pas qu'un allocateur à priorité sera systématiquement plus rapide, ni que le code généré sera toujours meilleur sur tout programme. Ce qu'ils suggèrent surtout, c'est qu'une simplification ciblée peut améliorer en même temps la taille de l'implémentation, le temps de compilation et certains indicateurs du code produit.
Le travail le plus rentable a consisté à désactiver les fonctionnalités de l'ancien allocateur une par une, puis mesurer l'effet. La coalescence et les préférences de registres expliquaient environ un tiers des instructions économisées. La prise en compte des trous dans les intervalles ajoutait environ 10 %, et le choix des débordements selon le poids des utilisations environ 5,5 %. Les préférences pour les registres physiques venaient ensuite, avec un gain plus modeste (autour de 1 %).
À l'inverse, une seconde tentative optimiste sur les plages débordées coûtait 37 % du temps de l'allocateur pour un gain d'environ 0,01 % sur les instructions. Recalculer une valeur au lieu de la recharger, ainsi qu'un cache d'emplacements de débordement, n'aidait pas de façon mesurable dans ces tests. Ces mécanismes ont été retirés.
Le coût assumé de l'absence d'éviction
Sans éviction, une décision prise tôt devient définitive. L'exemple d'une somme dans une boucle montre bien le défaut. Les valeurs temporaires de la boucle sont courtes et chaudes : elles passent avant des valeurs plus longues, comme le pointeur du tableau ou la limite de boucle. Elles finissent par prendre des registres que ces valeurs auraient préférés. L'allocateur génère alors quelques copies supplémentaires, placées en dehors de la boucle.
Un allocateur avec éviction pourrait déplacer une valeur déjà affectée pour rompre cette chaîne. Mais il faut alors gérer le déplacement, ses effets sur les autres intervalles, et parfois relancer des découpages. Dans le cas mesuré, le coût d'implémentation supplémentaire ne semblait pas justifié par la suppression de quelques copies froides.
C'est le point clé : une heuristique moins riche peut être un meilleur choix si ses erreurs sont rares ou peu coûteuses. Le bon réflexe, c'est de mesurer où elles apparaissent et si elles touchent du code réellement chaud, plutôt que d'ajouter une fonctionnalité « parce qu'un allocateur plus complet la possède ».
Conclusion : mesurer avant d'ajouter de la complexité
Cet allocateur montre qu'il n'est pas nécessaire de reproduire toutes les fonctionnalités d'un allocateur « industriel » pour obtenir un résultat solide. Des intervalles de vie bien définis, des trous conservés, une coalescence efficace, des préférences de registres et une estimation du coût des débordements apportent l'essentiel.
La démarche marche aussi au-delà des allocateurs : avant de porter ou de maintenir une fonctionnalité, mesurez ce qu'elle change vraiment. Repérez ce qui améliore le code chaud, ce qui ne bouge presque rien, et ce qui coûte plus qu'il n'apporte. Un système imparfait qui compile vite et produit un code correct vaut souvent mieux qu'un modèle plus élégant qui passe son temps à gérer des cas limites.
Pour aller plus loin, vous pouvez consulter l'article technique d'origine, ainsi que les travaux de référence sur l'allocation par parcours linéaire et l'allocateur greedy de LLVM. Le bon prochain pas consiste à appliquer la même discipline à votre propre compilateur : désactivez une fonctionnalité à la fois, mesurez le code généré et le temps de compilation, puis gardez ce qui améliore vraiment le système.
Comment les plages de vie et les contraintes sont calculées
Pour allouer correctement, l'allocateur doit savoir ce qui reste nécessaire en sortie de chaque bloc. Il peut calculer ces ensembles avec des itérations successives sur des bitsets, jusqu'à stabilisation. Ici, l'approche procède plutôt valeur par valeur : elle repère les blocs où une valeur est lue avant d'être écrite, puis remonte leurs prédécesseurs via une liste de travail. La remontée s'arrête dès qu'un bloc définit cette valeur.
Ce choix évite de payer un coût « global » basé sur toutes les combinaisons possibles (blocs × registres virtuels). Ce n'est pas une garantie automatique que ça sera toujours plus rapide : tout dépend de la forme du programme et de la manière dont les données sont représentées. Mais, pour le compilateur concerné, c'était une façon simple d'éviter de tout recalculer inutilement.
Une fois qu'il connaît les valeurs vivantes en sortie de bloc, l'allocateur parcourt les instructions à rebours et construit les segments d'intervalles. Le même parcours calcule aussi un poids pour chaque valeur, utilisé ensuite pour estimer le coût d'un débordement en mémoire.
Pondérer les utilisations selon les boucles
Chaque définition et chaque utilisation reçoit un poids, qui augmente avec la profondeur de boucle. En code linéaire, le poids est faible ; dans une boucle imbriquée, il monte. Dans l'implémentation décrite, le poids est multiplié par trois à chaque niveau, avec un plafond de profondeur.
L'idée est pragmatique : une instruction dans une boucle exécutée souvent coûte plus qu'une instruction sur un chemin rarement pris. Si une valeur utilisée à chaque tour de boucle est débordée, ses rechargements peuvent se répéter des milliers de fois. Dans ce cas, la conserver dans un registre peut valoir plus que d'économiser un accès mémoire isolé hors boucle.
Cela dit, les boucles donnent une approximation du nombre réel d'exécutions. Sans profilage, le compilateur ne sait pas toujours si une branche sera vraiment chaude. C'est donc une heuristique, pas une mesure.
Représenter les registres occupés par des masques
Les registres physiques sont numérotés et représentés par des masques de bits. Pour chaque position du programme, un masque indique quels registres sont indisponibles : parce qu'une instruction les utilise directement, ou parce qu'une autre valeur les occupe déjà .
Quand un bundle obtient un registre, l'allocateur ajoute ce registre à tous les masques couvrant ses segments. Les registres virtuels affectés et les registres physiques imposés par les instructions se retrouvent alors dans une représentation commune. Des masques résumés par groupes de 64 positions permettent de sauter rapidement les zones déjà occupées.
Les contraintes explicites couvrent notamment les registres d'arguments, ceux détruits par un appel, le registre de retour, et ceux utilisés par certaines opérations comme la division. L'idée est simple : rendre les conflits visibles dans les données, plutôt que de disperser des vérifications spéciales dans l'affectation.