Article de reference

Compilateur d'optimisation

Un compilateur optimisant est un compilateur conçu pour générer du code optimisé en minimisant notamment le temps d'exécution , l'utilisation de la mémoire , la taille du stocka...

Worldlex WikiFrancaisLecture gratuite

Un compilateur optimisant est un compilateur conçu pour générer du code optimisé en minimisant notamment le temps d'exécution , l'utilisation de la mémoire , la taille du stockage et la consommation d'énergie . L'optimisation est généralement mise en œuvre sous la forme d'une séquence de transformations optimisantes , également appelées optimisations du compilateur

Machine cible: La possibilité et l’opportunité d’appliquer certaines optimisations peuvent dépendre des caractéristiques de la machine cible. Certains compilateurs, tels que GCC et Clang, paramétrent des facteurs dépendants de la machine afin de permettre l’optimisation pour différentes machines.

Architecture du processeur cible

Nombre de registres : Les registres permettent d’optimiser les performances. Les variables locales peuvent être stockées dans des registres plutôt que dans la pile . Les résultats temporaires ou intermédiaires peuvent être accessibles depuis les registres plutôt que depuis la mémoire, plus lente.
RISC vs. CISC : Les jeux d’instructions CISC présentent souvent des longueurs d’instructions variables , un plus grand nombre d’instructions utilisables et un temps d’exécution variable pour chaque instruction. Les jeux d’instructions RISC s’efforcent de limiter cette variabilité : leur longueur est généralement constante, à quelques exceptions près ; le nombre de combinaisons d’opérations sur les registres et la mémoire est généralement plus faible ; et le taux d’émission des instructions (nombre d’instructions exécutées par période, généralement un multiple entier du cycle d’horloge) est généralement constant lorsque la latence mémoire est négligeable. Plusieurs méthodes permettent d’effectuer une tâche donnée, le CISC offrant généralement plus d’alternatives que le RISC. Les compilateurs doivent connaître le coût relatif des différentes instructions et choisir la séquence d’instructions optimale (voir la sélection des instructions ).
Pipelines : Un pipeline est un processeur décomposé en une chaîne de montage . Il permet d'utiliser différentes parties du processeur pour diverses instructions en divisant leur exécution en plusieurs étapes : décodage de l'instruction, décodage de l'adresse, accès à la mémoire, accès aux registres, calcul, écriture dans les registres, etc. Une instruction peut se trouver à l'étape d'écriture dans les registres, tandis qu'une autre peut être à l'étape d'accès aux registres. Des conflits de pipeline surviennent lorsqu'une instruction à une étape du pipeline dépend du résultat d'une autre instruction qui la précède dans le pipeline, mais qui n'est pas encore terminée. Ces conflits peuvent entraîner des blocages de pipeline : le processeur gaspille alors des cycles en attendant la résolution d'un conflit. Les compilateurs peuvent ordonner , ou réorganiser, les instructions afin de réduire la fréquence des blocages de pipeline.
Nombre d'unités fonctionnelles : Certains processeurs possèdent plusieurs unités arithmétiques et logiques (UAL) et unités de calcul en virgule flottante (UCF) leur permettant d'exécuter plusieurs instructions simultanément. Des restrictions peuvent s'appliquer quant aux instructions pouvant être appariées (l'« appariement » désigne l'exécution simultanée de deux instructions ou plus) et aux unités fonctionnelles pouvant exécuter chaque instruction. Ils peuvent également présenter des problèmes similaires aux conflits de pipeline. L'ordonnancement des instructions peut être optimisé afin de maximiser la charge des unités fonctionnelles.

Architecture machine

Taille et type du cache du processeur (à correspondance directe, associatif 2/4/8/16 voies, entièrement associatif) : des techniques telles que l’expansion en ligne et le déroulement de boucle peuvent augmenter la taille du code généré et réduire sa localité. Le programme peut ralentir considérablement si une section de code fréquemment utilisée (comme les boucles internes de divers algorithmes) ne tient plus dans le cache suite à des optimisations augmentant sa taille. De plus, les caches non entièrement associatifs présentent un risque accru de collisions, même lorsqu’ils ne sont pas remplis.
Taux de transfert cache/mémoire : ils indiquent au compilateur la pénalité en cas de défaut de cache. Cette fonctionnalité est principalement utilisée dans des applications spécialisées.

Usage prévu

Débogage : Lors du développement, les optimisations sont souvent désactivées pour accélérer la compilation ou faciliter le débogage du code exécutable. Les transformations d’optimisation, notamment celles qui réorganisent le code, peuvent rendre difficile la mise en relation du code exécutable avec le code source.
Utilisation générale : Les logiciels pré-packagés sont souvent conçus pour fonctionner sur diverses machines qui peuvent partager le même jeu d’instructions, mais présenter des performances différentes. Le code peut ne pas être optimisé pour une machine particulière ou être conçu pour fonctionner de manière optimale sur la machine la plus courante, au détriment des autres.
Utilisation à des fins spécifiques : si le logiciel est compilé pour des machines aux caractéristiques uniformes, le compilateur peut alors optimiser fortement le code généré pour ces machines.

Parmi les cas notables, citons le code conçu pour les processeurs parallèles et vectoriels , pour lequel des compilateurs de parallélisation spéciaux sont utilisés.

Le firmware d'un système embarqué peut être optimisé pour le processeur et la mémoire cibles. Le coût ou la fiabilité du système peuvent primer sur la vitesse d'exécution. Par exemple, les compilateurs pour logiciels embarqués proposent généralement des options permettant de réduire la taille du code au détriment de la vitesse. La prévisibilité du temps d'exécution du code étant souvent plus importante que sa rapidité maximale, la mise en cache du code peut être désactivée, de même que les optimisations du compilateur qui en dépendent.

Thèmes communs

L'optimisation englobe les thèmes suivants, parfois contradictoires.

Optimiser le cas commun: Le cas courant peut présenter des propriétés uniques permettant un chemin rapide au détriment d'un chemin plus lent . Si le chemin rapide est emprunté plus souvent, il en résulte de meilleures performances globales.
Évitez les redondances: Réutilisez les résultats déjà calculés et stockez-les pour une utilisation ultérieure, au lieu de les recalculer.
Moins de code: Supprimez les calculs inutiles et les valeurs intermédiaires. Moins de travail pour le processeur, le cache et la mémoire se traduit généralement par une exécution plus rapide. Par ailleurs, dans les systèmes embarqués , un code plus concis permet de réduire le coût du produit.
Moins de sauts grâce à l'utilisation de code linéaire , également appelé code sans branchement: Un code moins complexe. Les sauts ( branchements conditionnels ou inconditionnels ) interfèrent avec la prélecture des instructions, ce qui ralentit l'exécution. L'utilisation de l'inlining ou du déroulement de boucle permet de réduire les branchements, au prix d'une augmentation de la taille du fichier binaire proportionnelle à la longueur du code répété. Cela tend à fusionner plusieurs blocs de base en un seul.
Localité: Le code et les données qui sont accédés à peu près simultanément dans le temps doivent être placés à proximité les uns des autres en mémoire afin d'accroître la localité spatiale de la référence .
Exploiter la hiérarchie de la mémoire: Les accès à la mémoire sont de plus en plus coûteux à chaque niveau de la hiérarchie de la mémoire ; il convient donc de placer d’abord les éléments les plus fréquemment utilisés dans les registres, puis dans les caches, puis dans la mémoire principale, avant de les écrire sur le disque.
Paralléliser: Réorganiser les opérations pour permettre l'exécution parallèle de plusieurs calculs, que ce soit au niveau des instructions, de la mémoire ou des threads.
Des informations plus précises sont préférables: Plus les informations dont dispose le compilateur sont précises, mieux il pourra employer l'une ou l'ensemble de ces techniques d'optimisation.
Les métriques d'exécution peuvent être utiles: Les informations recueillies lors d'un test peuvent être utilisées pour l'optimisation guidée par profil . Les informations recueillies à l'exécution, idéalement avec une surcharge minimale , peuvent être utilisées par un compilateur JIT pour améliorer dynamiquement l'optimisation.
Réduction de la force: Remplacez les opérations complexes, difficiles ou coûteuses par des opérations plus simples. Par exemple, remplacez la division par une constante par une multiplication par son inverse, ou utilisez l'analyse par induction pour remplacer la multiplication par un indice de boucle par une addition.

Techniques spécifiques

Optimisations de boucle

:= 4*i + 1

fission de boucle ou distribution de boucle: La fission de boucle consiste à diviser une boucle en plusieurs boucles couvrant la même plage d'indices, chaque nouvelle boucle n'utilisant qu'une partie du corps de la boucle originale. Ceci permet d'améliorer la localité des références aux données accédées dans la boucle et au code contenu dans son corps.

fusion de boucles ou combinaison de boucles ou bourrage de boucles ou blocage de boucles: Une autre technique vise à réduire la surcharge des boucles. Lorsque deux boucles adjacentes s'exécuteraient le même nombre de fois, que ce nombre soit connu ou non à la compilation, leurs corps peuvent être combinés à condition qu'elles ne fassent pas référence aux données de l'autre.

Inversion de boucle: Cette technique transforme une boucle `while` standard en une boucle `do/while` (aussi appelée `repeat/until` ) intégrée dans une condition `if` , réduisant ainsi de deux le nombre d'itérations lors de l'exécution de la boucle. Bien que cela duplique la vérification de la condition (augmentant la taille du code), cette méthode est plus efficace car les itérations provoquent généralement un blocage du pipeline . De plus, si la condition initiale est connue à la compilation et qu'elle est sans effet de bord , la condition `if` peut être omise.

Échangeur de boucle: Ces optimisations inversent les boucles internes et externes. Lorsque les variables de boucle indexent un tableau, une telle transformation peut améliorer la localité des références, en fonction de la structure du tableau.

Mouvement de code invariant de boucle: Si une quantité est calculée à l'intérieur d'une boucle à chaque itération, et que sa valeur est identique pour chaque itération, il est possible d'améliorer considérablement l'efficacité en la déplaçant hors de la boucle et en calculant sa valeur une seule fois avant le début de la boucle. Ceci est particulièrement important pour les expressions de calcul d'adresse générées par les boucles sur les tableaux. Pour une implémentation correcte, cette technique doit être utilisée conjointement avec l'inversion de boucle , car tout le code ne peut pas être déplacé hors de la boucle en toute sécurité.

Optimisation des boucles imbriquées: Certains algorithmes omniprésents, comme la multiplication matricielle, présentent un comportement de cache très médiocre et un nombre excessif d'accès mémoire. L'optimisation des boucles imbriquées augmente le nombre d'accès au cache en opérant sur de petits blocs et en utilisant une permutation de boucles.

inversion de boucle: L'inversion de boucle inverse l'ordre d'affectation des valeurs à la variable d'index. Cette optimisation subtile permet d'éliminer les dépendances et, par conséquent, d'en autoriser d'autres. De plus, sur certaines architectures, l'inversion de boucle contribue à réduire la taille du code. En effet, lors de la décrémentation de l'index, la condition de sortie de la boucle est une comparaison avec zéro. Contrairement à une comparaison avec un nombre, qui nécessite ce paramètre, cette condition est souvent implémentée par une instruction spéciale sans paramètre. L'inversion de boucle permet ainsi de gagner de la mémoire en évitant le stockage du paramètre. Enfin, si le nombre à comparer dépasse la taille d'un mot de la plateforme, l'exécution d'une boucle standard nécessiterait l'exécution de plusieurs instructions pour évaluer la comparaison, ce qui n'est pas le cas avec l'inversion de boucle.

Déroulement de la boucle: Le déroulement de boucle duplique le corps de la boucle plusieurs fois afin de réduire le nombre de tests de la condition et le nombre de sauts. Ces tests et sauts peuvent nuire aux performances en perturbant le pipeline d'instructions. Il s'agit d'une optimisation visant à réduire le nombre de sauts. Le déroulement complet d'une boucle élimine toute surcharge, mais nécessite de connaître le nombre d'itérations à la compilation.

Division de boucle: Le fractionnement de boucle vise à simplifier une boucle ou à éliminer les dépendances en la divisant en plusieurs boucles ayant le même corps, mais itérant sur différentes portions contiguës de l'intervalle d'indices. Un cas particulier utile est le pelage de boucle , qui permet de simplifier une boucle présentant une première itération problématique en effectuant cette itération séparément avant d'entrer dans la boucle.

Décommutation de boucle: La fonction Unswitching déplace une conditionnelle de l'intérieur d'une boucle vers l'extérieur de celle-ci en dupliquant le corps de la boucle à l'intérieur de chacune des clauses if et else de la conditionnelle.

pipeline logiciel: La boucle est restructurée de manière à ce que le travail effectué lors d'une itération soit divisé en plusieurs parties et réalisé sur plusieurs itérations. Dans une boucle serrée, cette technique masque la latence entre le chargement et l'utilisation des valeurs.

Parallélisation automatique: Une boucle est convertie en code multithread ou vectorisé (ou même les deux) pour utiliser plusieurs processeurs simultanément dans une machine multiprocesseur à mémoire partagée (SMP), y compris les machines multicœurs.

Optimisations de magasin prévoyantes

si ( cond ) { foo (); } si ( cond ) { bar (); }// devient : si ( cond ) { foo (); bar (); }

et:

si ( cond ) { foo (); } si ( ! cond ) { bar (); }// devient : si ( cond ) { foo (); } sinon { bar (); }

Compression macro: Une optimisation spatiale qui identifie les séquences de code communes, crée des sous-programmes (« macros de code ») contenant ce code commun et remplace les occurrences de ces séquences par des appels aux sous-programmes correspondants. Cette optimisation est particulièrement efficace lorsqu'elle est réalisée directement en code machine , lorsque tout le code est présent. Cette technique a d'abord été utilisée pour économiser de l'espace dans un flux d'octets interprétatif , lors de l'implémentation de Macro Spitbol sur micro-ordinateurs . Le problème consistant à déterminer un ensemble optimal de macros minimisant l'espace requis par un segment de code donné est connu pour être NP-complet , mais des heuristiques efficaces permettent d'obtenir des résultats quasi optimaux.

Réduction des collisions de cache: (par exemple, en perturbant l'alignement au sein d'une page)

Réduction de la hauteur de la pile: Réorganiser un arbre d'expression pour minimiser les ressources nécessaires à l'évaluation de l'expression.

Réordonnancement des tests: Si deux tests conditionnent une condition, on peut commencer par les tests les plus simples (par exemple, comparer une variable à une autre) et ensuite seulement traiter les tests plus complexes (par exemple, ceux qui nécessitent un appel de fonction). Cette technique complète l'évaluation paresseuse , mais ne s'applique que lorsque les tests sont indépendants. La sémantique de court-circuitage peut compliquer son application.

Optimisations interprocédurales

L'optimisation interprocédurale s'applique à l'ensemble du programme, au-delà des limites des procédures et des fichiers. Elle fonctionne en étroite collaboration avec l'optimisation intraprocédurale, et repose sur la coopération d'une partie locale et d'une partie globale. Les optimisations interprocédurales typiques comprennent l'inclusion de procédures , l'élimination du code mort, la propagation des constantes et le réordonnancement des procédures. Comme toujours, le compilateur doit effectuer une analyse interprocédurale avant les optimisations proprement dites. Cette analyse inclut l'analyse des alias, l'analyse des accès aux tableaux et la construction du graphe d'appels .

L'optimisation interprocédurale est courante dans les compilateurs commerciaux modernes de SGI , Intel , Microsoft et Sun Microsystems . Le compilateur open source GCC a longtemps été critiqué pour son manque d'analyses et d'optimisations interprocédurales performantes, bien que la situation s'améliore actuellement. Open64 est un autre compilateur open source doté d'une infrastructure complète d'analyse et d'optimisation .

En raison du temps et de l'espace supplémentaires requis par l'analyse interprocédurale, la plupart des compilateurs ne l'effectuent pas par défaut. Les utilisateurs doivent utiliser explicitement les options du compilateur pour activer l'analyse interprocédurale et d'autres optimisations coûteuses.

Considérations pratiques

Un compilateur peut effectuer une large gamme d'optimisations, allant des optimisations simples et directes qui prennent peu de temps de compilation aux optimisations élaborées et complexes qui nécessitent un temps de compilation considérable. Par conséquent, les compilateurs proposent souvent des options dans leur commande ou procédure de contrôle afin de permettre à l'utilisateur de choisir le niveau d'optimisation souhaité ; par exemple, le compilateur IBM FORTRAN H permettait à l'utilisateur de spécifier aucune optimisation, une optimisation au niveau des registres uniquement, ou une optimisation complète. Dans les années 2000, il était courant que les compilateurs, tels que Clang , disposent de plusieurs options de commande permettant d'influer sur divers choix d'optimisation, à commencer par l' -O2option bien connue.

Une approche pour isoler l'optimisation consiste à utiliser des optimiseurs dits de post-passe (dont certaines versions commerciales remontent aux logiciels pour ordinateurs centraux de la fin des années 1970). Ces outils prennent le code exécutable généré par un compilateur optimisant et l'optimisent davantage. Les optimiseurs de post-passe agissent généralement au niveau du langage assembleur ou du code machine (contrairement aux compilateurs qui optimisent les représentations intermédiaires des programmes). On peut citer comme exemple le Portable C Compiler (PCC) des années 1980, qui proposait une passe optionnelle effectuant des post-optimisations sur le code assembleur généré.

Il convient également de noter que les algorithmes d'optimisation sont complexes et, notamment lorsqu'ils sont utilisés pour compiler des langages de programmation vastes et complexes, peuvent contenir des bogues introduisant des erreurs dans le code généré ou provoquant des erreurs internes lors de la compilation. Les erreurs de compilation, quelles qu'elles soient, peuvent être déconcertantes pour l'utilisateur, et particulièrement dans ce cas précis, car il peut être difficile d'identifier la logique d'optimisation en cause. En cas d'erreurs internes, le problème peut être partiellement atténué par une technique de programmation « à sécurité intégrée » : la logique d'optimisation du compilateur est alors codée de manière à intercepter toute erreur, à émettre un message d'avertissement et à poursuivre la compilation jusqu'à son terme.

Histoire

Les premiers compilateurs des années 1960 visaient principalement à compiler le code correctement et efficacement, le temps de compilation étant un enjeu majeur. Parmi les premiers compilateurs optimisants notables, on peut citer le compilateur IBM FORTRAN H de la fin des années 1960 Un autre compilateur optimisant important, pionnier de plusieurs techniques avancées, fut celui de BLISS (1970), décrit dans « The Design of an Optimizing Compiler » (1975) À la fin des années 1980, les compilateurs optimisants étaient suffisamment performants pour entraîner un déclin de la programmation en langage assembleur. Ce déclin a accompagné le développement des puces RISC et des fonctionnalités avancées des processeurs, telles que les processeurs superscalaires , l'exécution hors séquence et l'exécution spéculative , conçues pour être optimisées par les compilateurs plutôt que par le code assembleur écrit par des humains.