Principe de l'allocateur

Rat, petit compilateur backend, génère du code x86‑64 à partir d’une IR qui utilise un nombre illimité de registres virtuels (vregs). Le nouveau allocateur classe chaque vreg par importance et le place dans le premier registre physique disponible, soit un registre général (12 disponibles) soit un registre XMM (14 sous Linux). Si aucun registre n’est libre, le vreg est « spillé », c’est‑à‑dire stocké dans une case de pile, ce qui entraîne un store et un load. Le problème d’affectation optimale est NP‑difficile, d’où le recours à une heuristique de bin‑packing, proche de l’allocateur glouton d’LLVM mais sans ses parties les plus complexes.

/* avant allocation */
push rbp
mov rbp, rsp
sub rsp, 0x8
push rbx          ; rbx callee‑saved
mov rbx, rsi      ; y
call g            ; clobbers caller‑saved
add rax, rbx      ; t + y
pop rbx
leave
ret

L’exemple montre que cinq copies disparaissent et que la variable y, qui traverse l’appel, se retrouve automatiquement dans un registre callee‑saved, sans règle explicite dans l’algorithme.

Étapes de calcul et structures de données

L’allocateur s’exécute en cinq passes distinctes : Live ranges (numérotation des instructions, détermination des intervalles de vie), Fixed registers (marquage des registres déjà utilisés), Coalescing (fusion des vregs reliés par des copies), Picking registers (attribution des registres aux bundles selon l’importance) et Spilling (allocation de slots de pile et réécriture du code). Chaque bundle conserve son registre ou son slot pendant toute sa durée de vie, l’allocateur ne révoque jamais un registre attribué et ne divise pas un intervalle entre registre et mémoire.

Les intervalles sont exprimés en « slots » : chaque instruction i possède deux slots, lecture à 2i et écriture à 2i+1. Un intervalle est une liste triée de segments [début, fin]. Par exemple, le vreg v2 (argument y) vit de slot 3 à slot 13. Les masques de 64 bits représentent la disponibilité des registres par slot, ce qui permet de sauter rapidement 64 slots grâce à un masque résumé.

Le calcul du poids d’un vreg utilise la formule « déf ou utilisation ajoute 3·d », où d est la profondeur de boucle (max 11). Ainsi, une utilisation dans une boucle double ajoute 9 au poids, reflétant le coût d’un éventuel spill dans un contexte fortement itéré.

Analyse des performances et limites

Le nouveau code occupe 584 lignes contre 1392 lignes pour l’ancien allocateur linéaire, soit une réduction de 58 %. Les mesures internes indiquent que les cinq passes couvrent la majorité des travaux habituellement répartis sur de nombreux modules : l’absence d’éviction et de double passe réduit la complexité algorithmique, tandis que le coalescing élimine les copies redondantes dès la phase de fusion.

Cette approche présente toutefois des limites. Le modèle ne gère pas les cas où un vreg doit être partagé entre plusieurs registres à différents moments de son intervalle, ce qui peut conduire à des spills supplémentaires dans des fonctions très fragmentées. De plus, le poids basé uniquement sur la profondeur de boucle ne prend pas en compte le coût différentiel des accès mémoire versus registre dans les architectures modernes où le cache joue un rôle majeur.

En pratique, l’allocateur de Rat montre que, pour un compilateur de taille modeste, une heuristique simple mais bien instrumentée peut produire du code plus compact et plus rapide que des solutions linéaires plus lourdes, à condition d’accepter les compromis liés à l’absence d’éviction dynamique et à la granularité fixe des bundles.