Les développeurs de ZJIT, le compilateur Just-In-Time (JIT) pour Ruby, ont récemment intégré un nouvel allocateur de registres, une pièce maîtresse de l'optimisation du code machine. Cette avancée a été détaillée par Aaron Patterson, l'un des contributeurs clés du projet, dans une publication technique.

Qu'est-ce qu'un allocateur de registres ?

Lorsqu'un compilateur génère du code machine, il doit déterminer où placer les valeurs manipulées par le programme. Ces valeurs correspondent généralement à des variables ou à des résultats intermédiaires de calculs. Le processeur ne peut effectuer des opérations que sur des valeurs situées dans ses registres internes, bien que certaines architectures comme x86 autorisent des calculs sur des valeurs en mémoire. Toutefois, les accès aux registres sont nettement plus rapides que les accès à la mémoire, ce qui pousse les compilateurs à y conserver les valeurs le plus longtemps possible.

Un programme peut comporter un grand nombre de variables, mais le nombre de registres disponibles est limité et dépend de l'architecture. L'allocateur de registres examine l'ensemble des variables, décide dans quels registres elles doivent être placées et, si les ressources sont insuffisantes, détermine comment « déverser » (spill) ces variables dans la mémoire. Ce mécanisme est essentiel pour la performance du code généré.

La méthode retenue : l'analyse linéaire sur forme SSA

Plusieurs approches bien connues existent pour l'allocation de registres, avec des compromis entre le temps de compilation et la qualité du code produit. Pour ZJIT, l'équipe a choisi d'implémenter un allocateur linéaire (linear scan) basé sur une version réduite d'un article de Christian Wimmer intitulé « Linear Scan Register Allocation on SSA Form » (allocation linéaire de registres sur forme SSA).

ZJIT utilise en interne la forme statique à assignation unique (Static Single-Assignment form, ou SSA). Cette représentation du code impose qu'une variable ne soit assignée qu'une seule fois. Par exemple, le code Ruby suivant :

a = 123
a += 1
a

serait transformé, dans la représentation intermédiaire bas niveau (LIR) de ZJIT, en quelque chose comme :

v1 = Const(123)
v2 = Const(1)
v3 = Add v1, v2
CRet v3

Ici, v1, v2 et v3 sont des variables distinctes. La propriété SSA interdit toute réaffectation, contrairement au code Ruby original. Chaque variable SSA peut être lue autant de fois que nécessaire ; le point où elle est écrite est appelé « définition », et celui où elle est lue, « utilisation ».

Durées de vie et interférences

La première tâche de l'allocateur est de déterminer quand chaque valeur est « vivante » et pour combien de temps. Cette durée est appelée « durée de vie » ou « intervalle de vie » (live range). Elle commence à la définition de la valeur et se termine à sa dernière utilisation. Si deux valeurs ont des intervalles de vie qui se chevauchent, elles ne peuvent pas partager le même registre. Si davantage d'intervalles se chevauchent qu'il n'y a de registres disponibles, il faut déverser certaines valeurs en mémoire.

Prenons l'exemple d'une méthode Ruby déjà en forme SSA :

def add_twice(a, b, c)
  d = a + b
  e = d + c
  e
end

Les durées de vie des valeurs sont :

  • a : de l'entrée de fonction à l'instruction 1
  • b : idem
  • c : de l'entrée à l'instruction 2
  • d : de l'instruction 1 à l'instruction 2
  • e : de l'instruction 2 à l'instruction 3

Ainsi, à l'instruction 1, a et b meurent et d naît : on peut réutiliser un de leurs registres pour d. Seuls trois registres sont nécessaires à ce point.

Visualisation et débogage

ZJIT offre une option de débogage permettant d'afficher les graphiques d'intervalles de vie pour chaque bloc de base. Par exemple, la commande suivante :

$ ruby --zjit-call-threshold=2 --zjit-dump-lir=live_intervals ../test.rb

produit une sortie montrant, pour un bloc, les variables (numérotées v0, v1, etc.) et leurs états (v pour naissance, █ pour vie, ^ pour dernière utilisation) en regard des instructions LIR. Cette visualisation aide les développeurs à comprendre comment les valeurs interagissent et à valider le comportement de l'allocateur.

Graphes d'interférence

Une fois les durées de vie connues, l'allocateur évalue combien d'intervalles se chevauchent et où. Pour ce faire, il construit un « graphe d'interférence », un outil classique qui permet de décider de l'affectation des registres. Le travail détaillé sur ce graphe n'a pas été développé dans la publication, mais il s'agit d'une étape cruciale du processus.

Ce nouvel allocateur s'inscrit dans la volonté d'optimiser ZJIT, qui fait partie des efforts continus pour améliorer les performances de Ruby, en particulier dans les environnements à grande échelle comme celui de Shopify, où le projet est développé. Aucun chiffre de performance précis n'a été communiqué dans cette annonce technique.