Coloriages pour compilateurs
Jusqu’à présent, nous avons abordé les problématiques de traduction de langages de programmation haut-niveau vers l’assembleur en termes vagues et abstraits. Aujourd’hui, il est temps de préciser un peu un élément incontournable de cette traduction. En effet, nous avons vu dès le premier billet que les langages de programmation nous permettent de créer autant de variables que nous le souhaitons pour contenir les résultats intermédiaires de nos programmes. Cependant la machine ne possède qu’un nombre fini (une quinzaine) de cases mémoires immédiatement accessibles : les registres. La transformation des variables abstraites en registres physiques dans un programme est l’un des résultats fondamentaux de la compilation : c’est l’allocation de registres.
Allocation naïve
Dès le début, le problème s’annonce difficile : il est impossible d’attribuer un registre différent à chacune des variables de notre programme s’il y a plus de variables que de registres. Heureusement la machine nous offre un mécanisme de secours dans ce cas précis : nous pouvons attribuer aux variables surnuméraires un emplacement sur la pile. Il est temps d’illustrer tout ces concepts ; pour cela nous allons imaginer un petit langage de programmation très simple où l’on peut uniquement déclarer des variables et les additionner entre elles. Les idées présentées ici sont tout aussi valables (avec quelques raffinements) pour des langages plus compliqués. Voilà par exemple un programme dans ce langage:
x = 1;
y = 2;
z = x + y;
w = z + y;
return w;Après exécution, ce programme doit retourner 5. Supposons maintenant que notre machine dispose de trois registres A, B et C, et que l’on désigne un emplacement de la pile avec la notation Pile(n) où n est le numéro de l’emplacement. Ici, si l’on assigne un registre différent à chaque variable, on aura le programme suivant:
A = 1;
B = 2;
C = A + B;
Pile(0) = C + B;
return Pile(0);On pourrait se dire que le problème est réglé, et d’une certaine manière c’est vrai: l’exécution de ce programme avec registres alloués produira la bonne valeur 5. Néanmoins, il s’exécutera 100 fois plus lentement ! En effet, il est 100 fois plus rapide pour la machine d’écrire ou lire dans un registre que d’écrire ou lire sur la pile (qui se trouve dans la RAM). Ainsi la manière dont on alloue les registres a un énorme impact sur la performance du programme compilé. Il nous faut donc trouver une solution pour éviter d’allouer sur la pile autant que faire ce peu.
Dans cet exemple, on constate quelque chose d’intéressant: la variable x n’est plus utilisée après la ligne z = x + y, tandis que z n’apparaît pas avant cette ligne. L’idée est alors que z et x peuvent partager un même registre ! En effet, z = x + y va alors écraser la valeur de x mais cela est sans conséquence puisque l’on a plus besoin de la valeur de x par la suite.
Vie et mort des variables
Nous savons maintenant que certaines variables peuvent partager des registres. Mais il nous reste maintenant à déterminer quelles variables sont « compatibles » pour un tel partage. L’exemple précédent nous indique qu’il nous faut comprendre à quels endroit du programme les variables sont « nécessaires ». Afin de formaliser cela, il faut associer à chaque variable un ensemble d’instructions du programme dans lesquelles la variable est vivante, c’est à dire que l’on a besoin de connaître sa valeur afin d’effectuer nos calculs. Plus précisément, cet ensemble d’instructions est l’intervalle compris entre la première instruction qui définit la variable et la dernière instruction qui l’utilise. Voilà ce que ça donne sur notre exemple:
x | x = 1;
y | | y = 2;
z | | | z = x + y;
w | | | w = z + y;
| return w;On voit que ces intervalles se chevauchent. Si l’on y réfléchit bien, on remarque que lorsque deux intervalles se chevauchent et donc que deux variables sont vivantes en même temps, alors elles ne peuvent pas partager le même registre. En effet, si deux variables vivantes partagent le même registre, alors l’une des deux valeurs qu’elle contiennent va disparaître, et les instructions qui essaieront par la suite de lire cette valeur liront celle de l’autre variable.
On constate une autre chose de l’analyse de nos intervalles: il n’y a jamais plus de trois intervalles qui se chevauchent en même temps, jamais plus de trois variables qui sont vivantes en même temps. Cela nous conforte dans l’idée qu’il existe une manière d’allouer nos 3 registres sur ce programme sans utiliser la pile. Ici, il est facile de trouver la solution à la main : il suffit d’allouer C à la fois à x et à w dont les intervalles de vie sont disjoints. Mais il nous faut trouver une méthode systématique de prendre les décisions d’allocation, qui satisfasse les conditions suivantes:
- deux variables allouées au même registre doivent avoir des intervalles de vie disjoints;
- on veut utiliser le moins de registres possibles (pour éviter d’allouer sur la pile).
Coloriage de graphe
C’est ici que le mathématicien arrive pour débloquer la situation. Comme souvent en informatique ou en mathématique, il est nécessaire de voir le problème d’une autre façon afin d’en trouver la solution. Premièrement, on peut noter que nous n’avons pas besoin de connaître en détail les intervalles de chacune des variables; nous avons juste besoin de savoir lesquels se chevauchent. Ainsi nous allons construire à partir de nos intervalles un graphe appelé graphe d’interférence où chaque variable est un sommet. Deux variables sont reliées par une arrête dans le graphe d’interférence si leurs intervalles de vie se chevauchent. On dit alors qu’elles interfèrent. Voilà le graphe d’interférence de notre petit programme:
Chaque sommet est relié à au plus trois autres sommets du graphe, notre propriété de tout à l’heure est conservée. Mais quel est l’intérêt de construire un tel graphe ? Maintenant, il est possible de s’apercevoir que notre problème d’allocation de registres est équivalent à un problème de coloriage de graphe ! En effet, si on considère chacun de nos registres comme une « couleur », alors il nous faut « colorier » chacun des sommets du graphe d’interférence de telle sorte que deux sommets voisins ne soient pas de la même couleur. L’avantage est que le coloriage de graphe est un problème d’optimisation mathématique bien connu pour lequel il existe de nombreux algorithmes. Même si aucun algorithme de coloriage de graphe ne donne la solution optimale en un temps raisonnable (en trouver un reviendrait à démontrer que P = NP pour les connaisseurs), les algorithmes existants nous suffisent largement: ils offrent un bon équilibre entre vitesse d’exécution et optimalité de la solution trouvée.
Détailler ces algorithmes ici n’a que peu d’intérêt pour notre compréhension ; ce qu’il faut cependant retenir c’est la synergie entre informatique et mathématiques. Cette synergie s’est auparavant plutôt illustrée avec la combinatoire et les mathématiques discrètes, mais depuis une dizaine d’années ce sont les statistiques qui ont fait une entrée fracassante en informatique avec le Machine Learning. Comme en mathématiques, la capacité à abstraire et voir un même problème de différentes manières est essentielle.
Allocation dans le monde réel
Si notre petit exemple fait ressortir tous les concepts clés de l’allocation de registre, la solution présentée n’est pas du tout optimisée. En effet, on peut réduire la taille des intervalles à l’aide d’analyse de durée de vie plus fines, ajouter des raffinements au graphe d’interférence pour suggérer des affinités entre registres, etc. Dans les compilateurs Just in Time (JIT) où il faut compiler très rapidement, construire le graphe d’interférence est trop long et coûteux, et l’on a alors recours à des techniques en une seule passe (linear scan) plus rapides mais qui donnent une allocation moins optimale.
Une autre subtilité qui n’est pas mentionnée ici vient du fait que certains assembleurs comme l’x86 d’Intel exigent que les arguments ou résultats de certaines instructions soient stockés dans des registres spéciaux déterminés à l’avance. L’allocateur de registre doit alors prendre ça en compte. Pareillement, j’ai passé sous silence les complications de l’analyse de durée de vie qui se complique notablement lorsque le programme comporte des boucles.
L’allocation de registre est un problème commun à tous les compilateurs ; c’est pour éviter de la ré-implémenter à chaque fois que des compilateurs comme LLVM offrent un méta-assembleur possédant un nombre illimité de variables, vers lequel on peut traduire son langage haut niveau. De cette façon, LLVM s’occupe de l’allocation de registres pour vous.
Pour aller plus loin
- En 2006 une nouvelle avancée a été produite par des chercheurs de l’université de Karlsruhe : si l’on impose que chaque variable ne soit définie qu’une seule fois, alors le graphe d’interférence produit est cordal, débloquant ainsi tout une catégorie d’algorithmes de coloriage en temps polynomial. Cela illustre la puissance des théories mathématiques sous-jacentes à l’allocation de registre.
- LLVM n’a presque jamais utilisé de graphe d’interférence, préférant optimiser des algorithmes basés sur le linear scan ; ce post illustre assez bien le genre de problématiques que l’on peut rencontrer.
- Les slides du cours de compilation de François Pottier (analyse de durée de vie et coloriage du graphe d’interférence) adoptent un formalisme beaucoup plus rigoureux et détaillent des optimisations assez classiques.