Les compilateurs sont des programmes informatiques d’une importante complexité. Ils sont généralement structurés en une partie frontale, qui comprend le langage d’entrée, puis d’une partie arrière, qui s’occupe de traduire le programme d’entrée en du code binaire exécutable par le processeur. Les deux parties communiquent à l’aide d’une représentation intermédiaire (IR). Ainsi, pour qu’une même suite de compilateurs comprenne plusieurs langages et puisse générer du code pour plusieurs processeurs, il n’est pas nécessaire d’écrire un compilateur spécifique pour chaque paire langage-processeur : il suffit d’écrire les paires langage-IR et IR-processeur. Tout le travail effectué pour un processeur sera alors utilisable pour n’importe quel langage d’entrée.
Dès la génération du code intermédiaire, un compilateur utilise énormément de passes d’optimisation, afin de rendre le code plus rapide. Elle utilise des techniques comme la propagation des valeurs : si une variable a une valeur connue à un endroit du code (initialisation, condition…), alors cette valeur peut être propagée dans une série de calculs, qui seront alors effectués à la compilation au lieu de l’exécution. Ces passes sont effectuées en partie sur la représentation intermédiaire, pour les optimisations indépendantes du processeur, mais également sur du code machine déjà généré, pour tirer le meilleur parti possible du matériel.
Généralement, cette phase d’optimisation est extrêmement cruciale, étant donné que la représentation intermédiaire est suffisamment générale pour plusieurs types de processeurs et relativement simple dans les instructions disponibles : pour effectuer certaines opérations, il est parfois nécessaire d’écrire des dizaines d’instructions IR, alors que certains processeurs peuvent réaliser la même opération en une seule instruction. De plus, une représentation intermédiaire doit être prête pour les phases d’optimisation qui suivent, notamment en simplifiant toutes les étapes de raisonnement : dans les IR de type SSA, notamment, une variable ne peut être assignée qu’une seule fois, ce qui allonge d’autant plus le code.
Un nouvel optimiseur pour Visual C++
Le compilateur C++ de Microsoft, connu sous le nom de Visual C++, a longtemps été laissé dans un état proche de l’abandon. Depuis quelques années, les équipes de développement ont mis les bouchées doubles pour ramener le compilateur dans la course, avec une compatibilité avec les normes les plus récentes, au niveau de GCC ou Clang. Depuis lors, ils ont effectivement rattrapé en grande partie leur retard à ce niveau, mais pas encore pour les optimisations du code.
L’optimiseur actuel ne disposait que d’une série de transformations assez basiques, n’exploitant qu’une vue assez limitée des fonctions. Bon nombre d’optimisations fonctionnent en trouvant des motifs et en les remplaçant par une version améliorée, mais tous les motifs les plus utiles ne sont pas toujours implémentés. De plus, le code vectorisable n’est pas optimisé au meilleur de ses possibilités. Toutes ces limitations ont une origine historique : le compilateur C++ de Microsoft a des origines très anciennes, il provient de l’époque DOS où la mémoire était très limitée, ce qui limite les possibilités. Les efforts actuels portent principalement sur une modernisation du code, en éliminant les compromis d’un autre âge.
Le nouvel optimiseur exploite désormais une représentation intermédiaire SSA. Les algorithmes implémentés par-dessus peuvent ainsi être plus efficaces en temps par rapport aux approches par analyse du flux de données. Il se base sur une bibliothèque C++ avancée, exploitant les templates à foison, pour décrire les transformations à effectuer, ce qui a permis d’ajouter bon nombre d’optimisations simples en très peu de temps (surtout par rapport à l’infrastructure précédente).
Les développeurs de Visual C++ indiquent également avoir prêté attention à la correction de ces optimisations : il n’y a rien de plus désagréable que de passer des journées à déboguer son code pour trouver que, finalement, le problème n’est pas dû au code, mais bien au compilateur. Linus Torvalds a récemment torpillé GCC à ce sujet. Ici, les développeurs ont absolument cherché à éviter ces écueils, en testant leurs passes d’optimisation sur des programmes courants comme Chrome ou Firefox, puis sur des bibliothèques imposantes côté Microsoft comme CoreCLR ou Chakra.
Ils ont aussi employé des techniques de vérification formelle (à l’aide d’ALIVE et l’outil de démonstration automatique Z3, tous deux issus de Microsoft Research et aussi utilisés pour LLVM) et de la génération de code aléatoire avec Csmith (et C-Reduce pour réduire le code posant problème au strict minimum). Certains outils du projet LLVM ont pu être utilisés, puisque Visual C++ peut en exploiter les parties avant, comme Opt-fuzz, qui génère des expressions arithmétiques à optimiser.
Un exemple
Ces nouvelles optimisations peuvent avoir un effet assez radical sur certains bouts de code. Par exemple, pour un test de parité :
return a % 2 != 0 ? 4 : 2;
}
Les précédentes versions du compilateur produisaient un code qui prenait entre cinq et dix cycles en x86, selon que tout le processeur est exploité (prédiction du branchement parfaite) ou non :
and ecx, -2147483647
jge SHORT $LN3@test
dec ecx
or ecx, -2
inc ecx
$LN3@test:
test ecx, ecx
mov eax, 2
mov edx, 4
cmovne eax, edx
ret 0
Sauf que… Dans le test a % 2 == 0, le signe de a n’a aucune espèce d’importance, seul un bit est important : le modulo peut être remplacé par une opération logique, c’est-à -dire a & 1 == 0. Or, la comparaison implique un branchement dans le code, forcément lent sur les architectures x86 modernes : pour s’en débarrasser, la structure bool(a) ? C1 : C2 peut être remplacée par C2 + a*(C1-C2), c’est-à -dire exclusivement des calculs. Par conséquent, le nouveau code assembleur est le suivant :
and ecx, 1
lea eax, DWORD PTR [rcx*2+2]
ret 0
Celui-ci prend, à tous les coups, deux cycles d’horloge : par rapport à cinq à dix cycles, le gain est important, tant en rapidité qu’en taille de l’exécutable.
D’autres mécanismes effectuent une analyse statique du code, en précalculant autant de bits que possible dans les variables. Par exemple, lors d’une conversion vers un type plus grand, une série de bits est forcément à zéro, peu importe la valeur d’entrée. Ensuite, cette information peut être adaptée en fonction des opérations effectuées, ce qui peut guider le reste du processus.
short b = a; // b: 00000000________, a: ________
b <<= 4; // b: 0000________0000
b |= 3; // b: 0000________0011
return b != 0; // -> return true
}
Impact sur la taille du code généré
L’impact de ces modifications sur le code généré n’est pas facile à établir : certaines optimisations diminuent forcément la quantité de code, le compilateur sera alors plus enclin à recopier in extenso le code de petites fonctions pour éviter le surcoût dû à tout appel de fonction (qui n’est négligeable que pour des fonctions plus grandes) — ce qui conduit à l’augmentation de la taille du code. Il n’empêche, les résultats sont intéressants : sur tout Windows, c’est-à -dire plus d’un gigaoctet, les gains sont de 438 Ko par rapport à l’optimiseur précédent (0,3 %) ; sur SQL Server, 46 Ko sur 64 Mo (0,8 %) ; sur Chakra, le nouveau moteur JavaScript, 10 Ko sur 6 Mo (1,7 %).
En analysant plus en détail l’impact au niveau des instructions, les plus lentes sont largement évitées (branchements, multiplications, divisions), remplacées par des opérations plus rapides (comme des déplacements conditionnels). Les temps de compilation ont été impacté de diverses manières : une augmentation de 1,7 % pour Chrome ou une diminution de 2,6 % pour le noyau Windows.
Et alors ?
Les travaux sur l’optimiseur viennent seulement d’être annoncés : l’architecture choisie permettra aux développeurs d’ajouter des optimisations supplémentaires rapidement (et certaines sont déjà en cours de planification). Cet optimiseur devrait arriver dès Visual C++ 2015 Update 3, mais le travail continuera sur cet aspect du compilateur, afin de le rendre compétitif par rapport à ses concurrents, voire de les dépasser. Il est d’ores et déjà possible de le tester.
Source : Introducing a new, advanced Visual C++ code optimizer.
L’image a été créée par l’auteur et est soumise au droit d’auteur.