Discussion :

[dourouc05]

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é :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
int test(int a) {
    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 :

Code asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
?test@@YAHH@Z PROC
    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 :

Code asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
?test@@YAHH@Z PROC
    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.

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int test(unsigned char a) {
    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.
Ce contenu a été publié dans C++ par dourouc05.

[athlon64]

C'est du bon boulot.

Mais c'est dommage de toujours voir Microsoft dormir dans ses lauriers tant qu'il n' a pas de concurrence pour lui voler de part de marché...

"L'Apple de Steve Jobs" n'avait pas cette mentalité...

[MaximeCh]

Bonjour,

Je n'ai pas tout lu je suis perdu : quand on parle représentation intermédiaire ce n'est pas de l'assembleur? Ca a quelle forme?

[foetus]

quand on parle représentation intermédiaire ce n'est pas de l'assembleur? Ca a quelle forme?

C'est comme du bytecode Java

Et tu as un début de commencement de piste SSA

Et justement, si je ne dis pas de bêtises , dans les nouvelles normes C++ 17 19 22, ils veulent refaire le système d'include, un peu à la Java (dynamique versus statique). Mais parce que l'IR n'est pas normalisée, cela coince.

[dourouc05]

quand on parle représentation intermédiaire ce n'est pas de l'assembleur? Ca a quelle forme?

C'est un assembleur de haut niveau, qui comprend parfois la notion de fonction, mais n'a pas toutes les fonctionnalités d'un langage évolué (pas de conditions ou de boucles, mais bien des sauts).

Petit exemple en Julia. Tu as un bout de code comme 1+1, qui est traduit en langage intermédiaire par la commande @code_llvm 1+1 (ici, LLVM, avec un machin qui ressemble à une fonction et comprend la notion de type, par exemple entier sur 64 bits) :

Code x :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
define i64 @"julia_+_6364"(i64, i64) {
top:
  %2 = add i64 %1, %0
  ret i64 %2
}

Au contraire, en assembleur (@code_native 1+1), tu as des instructions de plus bas niveau (notamment pour gérer les appels de fonction), avec une perte de l'information de type :

Code asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
.text
        pushq   %rbp
        movq    %rsp, %rbp
        addq    %rdx, %rcx
        movq    %rcx, %rax
        popq    %rbp
        ret

dans les nouvelles normes C++ 17 19 22, ils veulent refaire le système d'include, un peu à la la Java (dynamique versus statique). Mais parce que l'IR n'est pas normalisée, cela coince si je ne me trompe pas

Si j'ai bien vu, pour les modules, ils ne prévoient pas un format standardisé (compatible entre compilateurs), "simplement" une syntaxe commune. Ces fichiers ne contiendraient pas de représentation intermédiaire, mais directement du code objet, qui serait utilisé un peu comme des bibliothèques partagées ou statiques. Sans garantie non plus ! Détails chez Microsoft : https://blogs.msdn.microsoft.com/vcb...2015-update-1/

[temoanatini]

encore un effort

[acx01b]

@dourouc05 : je ne dirais pas du tout assembleur, plutôt language bas niveau dans les instructions, mais de très haut niveau dans l'execution-flow.
notamment il travaille sur des graphes, après telle boucle, tel bloc d'instruction, puis tel appel récursif, le tout dans telle fonction, elle-même placée dans telle .dll, et le tout avec des problèmes de cache mémoire, de dépliement de boucles et d'appels récursifs, de simplification de tests redondants (notamment en C++ les type-check, genre dynamic-cast ou même appel virtuel), etc.

c'est notamment pour ça qu'il ne faut pas trop faire de "hacks" genre modifier un pointeur pour le remplacer par un int, etc. car sinon l'optimiseur ne comprend plus rien à l'execution-flow, voire se plante.

et pour conclure, c'est à cause de cet execution-flow que les bytecodes intermédiaires et les just-in-time compiler et les gestionnaires de mémoires sont intéressants, car en théorie ils sont capables de se servir du vrai execution-flow (qui dépend du contexte) pour optimiser certaines choses à l'exécution. (même si pour le moment ils sont loin d'être aussi élaborés : ils sont loin de "comprendre" le code)

[ChristianRoberge]

Enfin, Microsoft met le paquet pour améliorer le C++. Pourvu que cela ne s'arrête pas en chemin.