Optimisation du compilateur - Optimizing compiler

En informatique , un compilateur d'optimisation est un compilateur qui essaie de minimiser ou de maximiser certains attributs d'un programme informatique exécutable . Les exigences courantes consistent à minimiser le temps d'exécution d' un programme , l' empreinte mémoire , la taille de stockage et la consommation d' énergie (les trois derniers étant populaires pour les ordinateurs portables ).

L'optimisation du compilateur est généralement implémentée à l'aide d'une séquence de transformations d'optimisation , des algorithmes qui prennent un programme et le transforment pour produire un programme de sortie sémantiquement équivalent qui utilise moins de ressources ou s'exécute plus rapidement. Il a été montré que certains problèmes d'optimisation de code sont NP-complets , voire indécidables . En pratique, des facteurs tels que la volonté du programmeur d'attendre que le compilateur termine sa tâche imposent des limites supérieures aux optimisations qu'un compilateur peut fournir. L'optimisation est généralement un processus très gourmand en CPU et en mémoire. Dans le passé, les limitations de la mémoire de l'ordinateur étaient également un facteur majeur limitant les optimisations pouvant être effectuées.

En raison de ces facteurs, l'optimisation produit rarement une sortie « optimale », et en fait, une « optimisation » peut entraver les performances dans certains cas. Ce sont plutôt des méthodes heuristiques pour améliorer l'utilisation des ressources dans les programmes typiques.

Types d'optimisation

Les techniques utilisées dans l'optimisation peuvent être réparties entre différentes portées qui peuvent affecter n'importe quoi, d'une seule instruction à l'ensemble du programme. D'une manière générale, les techniques de portée locale sont plus faciles à mettre en œuvre que les techniques globales, mais entraînent des gains plus faibles. Voici quelques exemples de portées :

Optimisations des judas
Celles-ci sont généralement effectuées tard dans le processus de compilation après que le code machine a été généré. Cette forme d'optimisation examine quelques instructions adjacentes (comme « regarder à travers un judas » dans le code) pour voir si elles peuvent être remplacées par une seule instruction ou une séquence d'instructions plus courte. Par exemple, une multiplication d'une valeur par 2 peut être exécutée plus efficacement en déplaçant la valeur vers la gauche ou en ajoutant la valeur à elle-même (cet exemple est également un exemple de réduction de force ).
Optimisations locales
Ceux-ci ne prennent en compte que les informations locales à un bloc de base . Étant donné que les blocs de base n'ont pas de flux de contrôle, ces optimisations nécessitent très peu d'analyse, ce qui permet de gagner du temps et de réduire les besoins de stockage, mais cela signifie également qu'aucune information n'est conservée entre les sauts.
Optimisations globales
Celles-ci sont également appelées « méthodes intraprocédurales » et agissent sur des fonctions entières. Cela leur donne plus d'informations avec lesquelles travailler, mais rend souvent nécessaires des calculs coûteux. Les hypothèses les plus défavorables doivent être faites lorsque des appels de fonction se produisent ou que des variables globales sont consultées, car peu d'informations à leur sujet sont disponibles.
Optimisations de boucle
Ceux - ci agissent sur les déclarations qui constituent une boucle, comme une de boucle, par exemple le mouvement de code boucle invariant . Les optimisations de boucle peuvent avoir un impact significatif car de nombreux programmes passent un grand pourcentage de leur temps à l'intérieur des boucles.
Optimisations prémonitoires du magasin
Ceux-ci permettent aux opérations de stockage de se produire plus tôt que ce qui serait autrement autorisé dans le contexte des threads et des verrous. Le processus a besoin d'un moyen de savoir à l'avance quelle valeur sera stockée par l'affectation qu'il aurait dû suivre. Le but de cet assouplissement est de permettre à l'optimisation du compilateur d'effectuer certains types de réarrangement de code qui préservent la sémantique des programmes correctement synchronisés.
Optimisation interprocédurale, de l'ensemble du programme ou du temps de liaison
Ceux-ci analysent tout le code source d'un programme. La plus grande quantité d'informations extraites permet aux optimisations d'être plus efficaces que lorsqu'elles n'ont accès qu'à des informations locales, c'est-à-dire au sein d'une même fonction. Ce type d'optimisation peut également permettre la mise en œuvre de nouvelles techniques. Par exemple, function inlining , où un appel à une fonction est remplacé par une copie du corps de la fonction.
Optimisation du code machine et optimiseur de code objet
Ceux-ci analysent l'image de la tâche exécutable du programme après que tout un code machine exécutable a été lié . Certaines des techniques qui peuvent être appliquées dans une portée plus limitée, telles que la compression macro qui économise de l'espace en réduisant les séquences d'instructions communes, sont plus efficaces lorsque l'intégralité de l'image de la tâche exécutable est disponible pour analyse.

En plus des optimisations ciblées, il existe deux autres catégories générales d'optimisation :

Langage de programmation - indépendant ou dépendant du langage
La plupart des langages de haut niveau partagent des constructions et des abstractions de programmation communes : décision (if, switch, case), bouclage (for, while, repeat.. until, do.. while) et encapsulation (structures, objets). Ainsi, des techniques d'optimisation similaires peuvent être utilisées dans plusieurs langues. Cependant, certaines fonctionnalités du langage rendent certains types d'optimisations difficiles. Par exemple, l'existence de pointeurs en C et C++ rend difficile l'optimisation des accès aux tableaux (voir analyse d'alias ). Cependant, des langages tels que PL/1 (qui prend également en charge les pointeurs) disposent néanmoins de compilateurs d'optimisation sophistiqués pour obtenir de meilleures performances de diverses autres manières. A l'inverse, certaines fonctionnalités du langage facilitent certaines optimisations. Par exemple, dans certaines langues, les fonctions ne sont pas autorisées à avoir des effets secondaires . Par conséquent, si un programme effectue plusieurs appels à la même fonction avec les mêmes arguments, le compilateur peut immédiatement en déduire que le résultat de la fonction n'a besoin d'être calculé qu'une seule fois. Dans les langages où les fonctions sont autorisées à avoir des effets secondaires, une autre stratégie est possible. L'optimiseur peut déterminer quelle fonction n'a pas d'effets secondaires et restreindre ces optimisations aux fonctions sans effets secondaires. Cette optimisation n'est possible que lorsque l'optimiseur a accès à la fonction appelée.
Indépendant de la machine vs. dépendant de la machine
De nombreuses optimisations qui opèrent sur des concepts de programmation abstraits (boucles, objets, structures) sont indépendantes de la machine ciblée par le compilateur, mais bon nombre des optimisations les plus efficaces sont celles qui exploitent le mieux les fonctionnalités spéciales de la plate-forme cible. Des exemples sont des instructions qui font plusieurs choses à la fois, comme décrémenter le registre et se brancher sinon zéro.

Ce qui suit est une instance d'optimisation dépendante de la machine locale. Pour définir un registre sur 0, le moyen évident est d'utiliser la constante « 0 » dans une instruction qui définit une valeur de registre sur une constante. Un moyen moins évident est de XOR un registre avec lui-même. C'est au compilateur de savoir quelle variante d'instruction utiliser. Sur de nombreuses machines RISC , les deux instructions seraient également appropriées, car elles auraient toutes les deux la même longueur et prendraient le même temps. Sur de nombreux autres microprocesseurs tels que la famille Intel x86 , il s'avère que la variante XOR est plus courte et probablement plus rapide, car il n'y aura pas besoin de décoder un opérande immédiat, ni d'utiliser le "registre d'opérande immédiat" interne. Un problème potentiel avec ceci est que XOR peut introduire une dépendance de données sur la valeur précédente du registre, provoquant un blocage du pipeline . Cependant, les processeurs ont souvent XOR d'un registre avec lui-même comme cas particulier qui ne provoque pas de blocage.

Facteurs affectant l'optimisation

La machine elle-même
De nombreux choix concernant les optimisations qui peuvent et doivent être effectuées dépendent des caractéristiques de la machine cible. Il est parfois possible de paramétrer certains de ces facteurs dépendants de la machine, de sorte qu'un seul morceau de code du compilateur puisse être utilisé pour optimiser différentes machines en modifiant simplement les paramètres de description de la machine. GCC de GNU Project et Clang de LLVM Compiler Infrastructure sont des exemples d'optimisation de compilateurs qui suivent cette approche.
L'architecture du CPU cible
Nombre de registres CPU : Dans une certaine mesure, plus il y a de registres, plus il est facile d'optimiser les performances. Les variables locales peuvent être allouées dans les registres et non sur la pile . Les résultats temporaires/intermédiaires peuvent être laissés dans des registres sans écriture ni relecture de la mémoire.
  • RISC vs CISC : les jeux d'instructions CISC ont souvent des longueurs d'instructions variables, ont souvent un plus grand nombre d'instructions possibles qui peuvent être utilisées, et chaque instruction peut prendre des quantités de temps différentes. Les jeux d'instructions RISC tentent de limiter la variabilité de chacun d'entre eux : les jeux d'instructions sont généralement de longueur constante, à quelques exceptions près, il y a généralement moins de combinaisons de registres et d'opérations de mémoire, et le taux d'émission d'instructions généralement un multiple entier du cycle d'horloge) est généralement constante dans les cas où la latence de la mémoire n'est pas un facteur. Il peut y avoir plusieurs façons d'effectuer une certaine tâche, CISC offrant généralement plus d'alternatives que RISC. Les compilateurs doivent connaître les coûts relatifs entre les différentes instructions et choisir la meilleure séquence d'instructions (voir sélection d'instructions ).
  • Pipelines : Un pipeline est essentiellement un processeur divisé en une chaîne de montage . Il permet d'utiliser des parties du processeur pour différentes instructions en divisant l'exécution des instructions en différentes étapes : décodage d'instructions, décodage d'adresse, récupération de mémoire, récupération de registre, calcul, stockage de registre, etc. Une instruction peut être dans l'étape de stockage de registre. , tandis qu'un autre pourrait être en phase d'extraction de registre. Les conflits de pipeline se produisent lorsqu'une instruction dans une étape du pipeline dépend du résultat d'une autre instruction la précédant dans le pipeline mais pas encore terminée. Les conflits de pipeline peuvent conduire à des blocages de pipeline : où le CPU gaspille des cycles en attendant qu'un conflit soit résolu.
Les compilateurs peuvent planifier ou réorganiser les instructions afin que les blocages de pipeline se produisent moins fréquemment.
  • Nombre d'unités fonctionnelles : Certaines CPU possèdent plusieurs ALU et FPU . Cela leur permet d'exécuter plusieurs instructions simultanément. Il peut y avoir des restrictions sur les instructions qui peuvent s'apparier avec quelles autres instructions ("l'appariement" est l'exécution simultanée de deux instructions ou plus), et quelle unité fonctionnelle peut exécuter quelle instruction. Ils ont également des problèmes similaires aux conflits de pipeline.
Là encore, les instructions doivent être programmées pour que les différentes unités fonctionnelles soient pleinement alimentées en instructions à exécuter.
L'architecture de la machine
  • Taille et type du cache (256 kiB à 12 Mio) (mappé directement, 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 la localité du code. Le programme peut ralentir considérablement si une section de code très utilisée (comme les boucles internes dans divers algorithmes) ne peut soudainement plus tenir dans le cache. De plus, les caches qui ne sont pas entièrement associatifs ont de plus grandes chances de collisions de cache, même dans un cache non rempli.
  • Taux de transfert de cache/mémoire : ils donnent au compilateur une indication de la pénalité pour les échecs de cache. Ceci est principalement utilisé dans des applications spécialisées.
Utilisation prévue du code généré
Débogage
Lors de l'écriture d'une application, un programmeur recompilera et testera souvent, et la compilation doit donc être rapide. C'est l'une des raisons pour lesquelles la plupart des optimisations sont délibérément évitées pendant la phase de test/débogage. De plus, le code du programme est généralement " pas à pas " (voir Animation du programme ) à l'aide d'un débogueur symbolique , et l'optimisation des transformations, en particulier celles qui réorganisent le code, peut rendre difficile la relation entre le code de sortie et les numéros de ligne du code source d'origine. Cela peut dérouter à la fois les outils de débogage et les programmeurs qui les utilisent.
Usage général
On s'attend très souvent à ce que les logiciels préemballés soient exécutés sur une variété de machines et de processeurs qui peuvent partager le même jeu d'instructions, mais qui ont des caractéristiques de synchronisation, de cache ou de mémoire différentes. En conséquence, le code peut ne pas être adapté à un processeur en particulier, ou peut être adapté pour fonctionner au mieux sur le processeur le plus populaire tout en fonctionnant de manière acceptable sur d'autres processeurs.
Utilisation spéciale
Si le logiciel est compilé pour être utilisé sur une ou quelques machines très similaires, avec des caractéristiques connues, alors le compilateur peut fortement ajuster le code généré à ces machines spécifiques, à condition que de telles options soient disponibles. Les cas spéciaux importants incluent le code conçu pour les processeurs parallèles et vectoriels , pour lesquels des compilateurs de parallélisation spéciaux sont utilisés.
Systèmes embarqués
Il s'agit d'un cas courant d'utilisation à des fins spéciales. Le logiciel embarqué peut être étroitement réglé sur une taille exacte de processeur et de mémoire. De plus, le coût ou la fiabilité du système peut être plus important que la vitesse du code. Par exemple, les compilateurs pour logiciels embarqués offrent généralement des options qui réduisent la taille du code au détriment de la vitesse, car la mémoire est le coût principal d'un ordinateur embarqué. La synchronisation du code peut devoir être prévisible, plutôt qu'aussi rapide que possible, de sorte que la mise en cache du code peut être désactivée, ainsi que les optimisations du compilateur qui l'exigent.

Thèmes communs

Dans une large mesure, les techniques d'optimisation du compilateur ont les thèmes suivants, qui sont parfois en conflit.

Optimiser le cas courant
Le cas courant peut avoir des propriétés uniques qui permettent un chemin rapide au détriment d'un chemin lent . Si la voie rapide est empruntée le plus souvent, le résultat est de meilleures performances globales.
Éviter la redondance
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 entraîne généralement une exécution plus rapide. Alternativement, dans les systèmes embarqués , moins de code entraîne un coût de produit inférieur.
Moins de sauts en utilisant le code en ligne droite , également appelé code sans branche
Code moins compliqué. Les sauts ( branches conditionnelles ou inconditionnelles ) interfèrent avec la prélecture des instructions, ralentissant ainsi le code. L'utilisation de l'inlining ou du déroulement de boucle peut réduire les branchements, au prix d'une augmentation de la taille du fichier binaire de la longueur du code répété. Cela tend à fusionner plusieurs blocs de base en un seul.
Localité
Le code et les données auxquels on accède étroitement dans le temps doivent être placés à proximité les uns des autres dans la mémoire pour augmenter la localité spatiale de référence .
Exploiter la hiérarchie de la mémoire
Les accès à la mémoire sont de plus en plus coûteux pour chaque niveau de la hiérarchie mémoire , placez donc d'abord les éléments les plus couramment utilisés dans les registres, puis les caches, puis la mémoire principale, avant d'aller sur disque.
Paralléliser
Réorganisez les opérations pour permettre à plusieurs calculs de se dérouler en parallèle, soit au niveau de l'instruction, de la mémoire ou du thread.
Des informations plus précises, c'est mieux
Plus les informations dont dispose le compilateur sont précises, mieux il peut utiliser l'une ou l'ensemble de ces techniques d'optimisation.
Les métriques d'exécution peuvent aider
Les informations recueillies lors d'un test peuvent être utilisées dans l' optimisation guidée par profil . Les informations recueillies au moment de 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 ou difficiles ou coûteuses par des opérations plus simples. Par exemple, remplacer la division par une constante par la multiplication par sa réciproque, ou utiliser l' analyse des variables d'induction pour remplacer la multiplication par un indice de boucle avec addition.

Techniques spécifiques

Optimisations de boucle

Article principal : Optimisation des boucles

Certaines techniques d'optimisation principalement conçues pour fonctionner sur des boucles comprennent :

Analyse des variables d'induction
En gros, si une variable dans une boucle est une simple fonction linéaire de la variable d'index, telle que j := 4*i + 1, elle peut être mise à jour de manière appropriée chaque fois que la variable de boucle est modifiée. Il s'agit d'une réduction de force , et peut également permettre aux définitions de la variable d'index de devenir du code mort . Ces informations sont également utiles pour la vérification des limites et l' analyse de dépendance , entre autres.
Fission en boucle ou distribution en boucle
La fission de boucle tente de diviser une boucle en plusieurs boucles sur la même plage d'index, mais chacune ne prenant qu'une partie du corps de la boucle. Cela peut améliorer la localité de référence , à la fois les données accessibles dans la boucle et le code dans le corps de la boucle.
Fusion de boucles ou combinaison de boucles ou ramming de boucles ou brouillage de boucles
Une autre technique qui tente de réduire la surcharge de boucle. Lorsque deux boucles adjacentes itéreraient le même nombre de fois, que ce nombre soit connu ou non au moment de la compilation, leurs corps peuvent être combinés tant qu'ils ne font 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 (également connue sous le nom de repeat/until ) enveloppée dans une condition if , réduisant le nombre de sauts de deux, pour les cas où la boucle est exécutée. Cela duplique la vérification des conditions (augmentant la taille du code), mais est plus efficace car les sauts provoquent généralement un blocage du pipeline . De plus, si la condition initiale est connue au moment de la compilation et est connue pour être sans effet secondaire , la garde if peut être ignorée.
Échange de boucle
Ces optimisations échangent des boucles internes avec des boucles externes. Lorsque les variables de boucle indexent dans un tableau, une telle transformation peut améliorer la localité de référence, selon la disposition du tableau.
Mouvement de code invariant en boucle
Si une quantité est calculée à l'intérieur d'une boucle à chaque itération et que sa valeur est la même à chaque itération, cela peut grandement améliorer l'efficacité de la sortir de la boucle et de calculer sa valeur une seule fois avant le début de la boucle. Ceci est particulièrement important avec les expressions de calcul d'adresse générées par des boucles sur des tableaux. Pour une implémentation correcte, cette technique doit être utilisée avec l' inversion de boucle , car tout le code ne peut pas être hissé en toute sécurité en dehors de la boucle.
Optimisation de l'imbrication de boucle
Certains algorithmes omniprésents tels que la multiplication matricielle ont un comportement de cache très médiocre et des accès mémoire excessifs. L'optimisation de l'imbrication de boucles augmente le nombre d'accès au cache en effectuant l'opération sur de petits blocs et en utilisant un échange de boucles.
Inversion de boucle
L'inversion de boucle inverse l'ordre dans lequel les valeurs sont affectées à la variable d'index. Il s'agit d'une optimisation subtile qui peut aider à éliminer les dépendances et ainsi permettre d'autres optimisations. De plus, sur certaines architectures, l'inversion de boucle contribue à réduire la taille du code, car lorsque l'index de boucle est décrémenté, la condition qui doit être remplie pour que le programme en cours quitte la boucle est une comparaison avec zéro. Il s'agit souvent d'une instruction spéciale sans paramètre, contrairement à une comparaison avec un nombre, qui a besoin du nombre à comparer. Par conséquent, le nombre d'octets nécessaires pour stocker le paramètre est enregistré en utilisant l'inversion de boucle. De plus, si le nombre de comparaison dépasse la taille du mot de la plate-forme, dans l'ordre de boucle standard, plusieurs instructions devraient être exécutées afin d'évaluer la comparaison, ce qui n'est pas le cas avec l'inversion de boucle.
Déroulement de la boucle
Le déroulement duplique le corps de la boucle plusieurs fois, afin de réduire le nombre de fois que la condition de boucle est testée et le nombre de sauts, ce qui nuit aux performances en altérant le pipeline d'instructions. Une optimisation "moins de sauts". Le déroulement complet d'une boucle élimine toute surcharge, mais nécessite que le nombre d'itérations soit connu au moment de la compilation.
Fractionnement de boucle
Le fractionnement de boucle tente de simplifier une boucle ou d'éliminer les dépendances en la divisant en plusieurs boucles qui ont le même corps mais qui itèrent sur différentes parties contiguës de la plage d'index. Un cas particulier utile est le pelage de boucle , qui peut simplifier une boucle avec une première itération problématique en effectuant cette itération séparément avant d'entrer dans la boucle.
Désactivation de la boucle
La désactivation déplace un conditionnel de l'intérieur d'une boucle vers l'extérieur de la boucle en dupliquant le corps de la boucle à l'intérieur de chacune des clauses if et else du conditionnel.
Pipeline de logiciels
La boucle est restructurée de manière à ce que le travail effectué dans une itération soit divisé en plusieurs parties et effectué 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) afin d'utiliser plusieurs processeurs simultanément dans une machine multiprocesseur à mémoire partagée (SMP), y compris des machines multicœurs.

Optimisations des flux de données

Les optimisations de flux de données , basées sur l'analyse de flux de données , dépendent principalement de la façon dont certaines propriétés des données sont propagées par les bords de contrôle dans le graphe de flux de contrôle . Certains d'entre eux incluent :

Élimination des sous-expressions communes
Dans l'expression (a + b) - (a + b)/4, "sous-expression commune" fait référence au fichier (a + b). Les compilateurs implémentant cette technique réalisent que (a + b)cela ne changera pas et ne calculent donc sa valeur qu'une seule fois.
Pliage et propagation constants
remplacer les expressions constituées de constantes (par exemple, 3 + 5) par leur valeur finale ( 8) au moment de la compilation, plutôt que d'effectuer le calcul au moment de l'exécution. Utilisé dans la plupart des langues modernes.
Reconnaissance et élimination des variables d'induction
voir la discussion ci-dessus sur l' analyse des variables d'induction .
Classification d'alias et analyse de pointeurs
en présence de pointeurs , il est difficile de faire des optimisations, car potentiellement n'importe quelle variable peut avoir été modifiée lorsqu'un emplacement mémoire est affecté. En spécifiant quels pointeurs peuvent alias quelles variables, les pointeurs non liés peuvent être ignorés.
Élimination du magasin mort
suppression des affectations aux variables qui ne sont pas lues par la suite, soit parce que la durée de vie de la variable se termine, soit à cause d'une affectation ultérieure qui écrasera la première valeur.

Optimisations basées sur SSA

Ces optimisations sont destinées à être effectuées après avoir transformé le programme en une forme spéciale appelée Static Single Assignment , dans laquelle chaque variable est affectée à un seul endroit. Bien que certains fonctionnent sans SSA, ils sont plus efficaces avec SSA. De nombreuses optimisations répertoriées dans d'autres sections bénéficient également sans modifications particulières, telles que l'allocation de registres.

Numérotation des valeurs globales
GVN élimine la redondance en construisant un graphique de valeurs du programme, puis en déterminant quelles valeurs sont calculées par des expressions équivalentes. GVN est capable d'identifier une redondance que l'élimination de sous-expression commune ne peut pas, et vice versa.
Propagation constante conditionnelle creuse
Combine la propagation constante, le repliement constant et l' élimination du code mort , et améliore ce qui est possible en les exécutant séparément. Cette optimisation exécute symboliquement le programme, en propageant simultanément des valeurs constantes et en éliminant des portions du graphe de flux de contrôle que cela rend inaccessibles.

Optimisations du générateur de code

Affectation du registre
Les variables les plus fréquemment utilisées doivent être conservées dans les registres du processeur pour un accès plus rapide. Pour trouver quelles variables mettre dans les registres, un graphique d'interférence est créé. Chaque variable est un sommet et lorsque deux variables sont utilisées en même temps (ont une plage d'intersection entre elles), elles ont un bord entre elles. Ce graphe est coloré en utilisant par exemple l'algorithme de Chaitin utilisant le même nombre de couleurs qu'il y a de registres. Si la coloration échoue, une variable est "déversée" en mémoire et la coloration est retentée.
Sélection d'instructions
La plupart des architectures, en particulier les architectures CISC et celles avec de nombreux modes d'adressage , offrent plusieurs manières différentes d'effectuer une opération particulière, en utilisant des séquences d'instructions entièrement différentes. Le travail du sélecteur d'instructions est de faire un bon travail dans l'ensemble en choisissant quelles instructions implémenter avec quels opérateurs dans la représentation intermédiaire de bas niveau . Par exemple, sur de nombreux processeurs de la famille 68000 et sur l'architecture x86, des modes d'adressage complexes peuvent être utilisés dans des instructions telles que "lea 25(a1,d5*4), a0", permettant à une seule instruction d'effectuer une quantité importante d'arithmétique avec moins de rangement.
Planification des instructions
La planification des instructions est une optimisation importante pour les processeurs pipelines modernes, qui évite les blocages ou les bulles dans le pipeline en regroupant les instructions sans dépendances, tout en veillant à préserver la sémantique d'origine.
Rematérialisation
La rematérialisation recalcule une valeur au lieu de la charger depuis la mémoire, empêchant un accès mémoire. Ceci est effectué en tandem avec l'allocation des registres pour éviter les débordements.
Affacturage du code
Si plusieurs séquences de code sont identiques, ou peuvent être paramétrées ou réordonnées pour être identiques, elles peuvent être remplacées par des appels à un sous-programme partagé. Cela peut souvent partager le code pour la configuration des sous-programmes et parfois la récursivité de la queue.
Trampolines
De nombreux processeurs ont des instructions d'appel de sous-programme plus petites pour accéder à une mémoire insuffisante. Un compilateur peut économiser de l'espace en utilisant ces petits appels dans le corps principal du code. Les instructions de saut en mémoire faible peuvent accéder aux routines à n'importe quelle adresse. Cela multiplie les économies d'espace grâce à la factorisation du code.
Réorganiser les calculs
Basés sur la programmation linéaire en nombres entiers , les compilateurs de restructuration améliorent la localisation des données et exposent davantage de parallélisme en réordonnant les calculs. Les compilateurs optimisant l'espace peuvent réorganiser le code pour allonger les séquences qui peuvent être factorisées dans des sous-routines.

Optimisations du langage fonctionnel

Bien que beaucoup d'entre eux s'appliquent également aux langages non fonctionnels, ils proviennent ou sont particulièrement critiques dans les langages fonctionnels tels que Lisp et ML .

Optimisation des appels de queue
Un appel de fonction consomme de l'espace dans la pile et implique une surcharge liée à la transmission de paramètres et au vidage du cache d'instructions. Les algorithmes récursifs de queue peuvent être convertis en itération via un processus appelé élimination de la récursivité de queue ou optimisation d'appel de queue.
Déforestation ( fusion de structure de données )
Dans les langages où il est courant qu'une séquence de transformations soit appliquée à une liste, la déforestation tente de supprimer la construction de structures de données intermédiaires.
Évaluation partielle

Autres optimisations

Élimination du contrôle des limites
De nombreux langages, tels que Java , appliquent la vérification des limites de tous les accès aux tableaux. Il s'agit d'un grave goulot d' étranglement des performances sur certaines applications telles que le code scientifique. L'élimination de la vérification des limites permet au compilateur de supprimer en toute sécurité la vérification des limites dans de nombreuses situations où il peut déterminer que l'index doit se situer dans des limites valides ; par exemple, s'il s'agit d'une simple variable de boucle.
Optimisation du décalage des branches (selon la machine)
Choisissez le déplacement de branche le plus court qui atteint la cible.
Réorganisation des blocs de code
La réorganisation des blocs de code modifie l'ordre des blocs de base dans un programme afin de réduire les branchements conditionnels et d'améliorer la localité de référence.
Élimination du code mort
Supprime les instructions qui n'affecteront pas le comportement du programme, par exemple les définitions qui n'ont aucune utilité, appelées code mort . Cela réduit la taille du code et élimine les calculs inutiles.
Factorisation des invariants ( invariants de boucle )
Si une expression est exécutée à la fois lorsqu'une condition est remplie et qu'elle ne l'est pas, elle ne peut être écrite qu'une seule fois en dehors de l'instruction conditionnelle. De même, si certains types d'expressions (par exemple, l'affectation d'une constante dans une variable) apparaissent à l'intérieur d'une boucle, elles peuvent en être retirées car leur effet sera le même, peu importe qu'elles soient exécutées plusieurs fois ou une seule fois. . Ceci est également connu sous le nom d'élimination totale de la redondance. Une optimisation similaire mais plus puissante est l'élimination partielle de la redondance (PRE).
Extension en ligne ou extension macro
Lorsqu'un code invoque une procédure , il est possible d'insérer directement le corps de la procédure à l'intérieur du code appelant plutôt que de lui transférer le contrôle. Cela permet d'économiser les frais généraux liés aux appels de procédure, tout en offrant la possibilité de nombreuses optimisations spécifiques aux paramètres différents, mais au détriment de l'espace ; le corps de la procédure est dupliqué chaque fois que la procédure est appelée en ligne. En règle générale, l'incorporation est utile dans le code critique pour les performances qui effectue un grand nombre d'appels à de petites procédures. Une optimisation "moins de sauts". Les énoncés des langages de programmation impératifs sont également un exemple d'une telle optimisation. Bien que les instructions puissent être implémentées avec des appels de fonction, elles sont presque toujours implémentées avec du code inlining.
Enfilage de saut
Dans cette optimisation, des sauts conditionnels consécutifs fondés entièrement ou partiellement sur la même condition sont fusionnés.
Par exemple, à ,if (c) { foo; } if (c) { bar; }if (c) { foo; bar; }
et à .if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }
Compression de macros
Une optimisation de l'espace qui reconnaît les séquences de code communes, crée des sous-programmes ("macros de code") qui contiennent le code commun et remplace les occurrences des séquences de code communes par des appels aux sous-programmes correspondants. Cela se fait le plus efficacement en tant qu'optimisation du code machine , lorsque tout le code est présent. La technique a d'abord été utilisée pour économiser de l'espace dans un flux d'octets interprétatif utilisé dans une implémentation de Macro Spitbol sur des micro-ordinateurs . Le problème de la détermination d'un ensemble optimal de macros qui minimise l'espace requis par un segment de code donné est connu pour être NP-complet , mais des heuristiques efficaces atteignent des résultats presque optimaux.
Réduction des collisions de cache
(par exemple, en perturbant l'alignement dans une page)
Réduction de la hauteur de la pile
Réorganisez l'arborescence des expressions pour minimiser les ressources nécessaires à l'évaluation des expressions.
Tester la réorganisation
Si nous avons deux tests qui sont la condition de quelque chose, nous pouvons d'abord traiter les tests les plus simples (par exemple, comparer une variable à quelque chose) et ensuite seulement les tests complexes (par exemple, ceux qui nécessitent un appel de fonction). Cette technique complète l' évaluation paresseuse , mais ne peut être utilisée que lorsque les tests ne sont pas dépendants les uns des autres. Une sémantique court-circuitée peut rendre cela difficile.

Optimisations interprocédurales

L'optimisation interprocédurale fonctionne sur l'ensemble du programme, au-delà des limites des procédures et des fichiers. Il travaille en étroite collaboration avec des homologues intraprocédurales, réalisé avec la coopération d'une partie locale et d'une partie globale. Les optimisations interprocédurales typiques sont : l' incorporation de procédures , l'élimination du code mort interprocédural, la propagation constante interprocédurale et la réorganisation des procédures . Comme d'habitude, le compilateur doit effectuer une analyse interprocédurale avant ses optimisations réelles. Les analyses interprocédurales incluent l'analyse d'alias, l'analyse d'accès au tableau et la construction d'un graphe d'appels .

L'optimisation interprocédurale est courante dans les compilateurs commerciaux modernes de SGI , Intel , Microsoft et Sun Microsystems . Pendant longtemps, le GCC open source a été critiqué pour son manque d'analyses et d'optimisations interprocédurales puissantes, bien que cela s'améliore maintenant. Un autre compilateur open source avec une infrastructure complète d'analyse et d'optimisation est Open64 .

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

Considérations pratiques

Il peut y avoir un large éventail d'optimisations qu'un compilateur peut effectuer, allant des plus simples et directes qui prennent peu de temps de compilation aux plus élaborées et complexes qui impliquent des quantités considérables de temps de compilation. En conséquence, les compilateurs fournissent souvent des options à leur commande ou procédure de contrôle pour permettre à l'utilisateur du compilateur de choisir le niveau d'optimisation à demander ; par exemple, le compilateur IBM FORTRAN H permettait à l'utilisateur de ne spécifier aucune optimisation, une optimisation au niveau des registres uniquement, ou une optimisation complète. Dans les années 2000, il était courant pour les compilateurs, tels que Clang , d'avoir un certain nombre d'options de commande de compilateur qui pouvaient affecter une variété de choix d'optimisation, à commencer par le -O2commutateur familier .

Une approche pour isoler l'optimisation est l'utilisation d' optimiseurs dits post-pass (dont certaines versions commerciales remontent aux logiciels mainframe de la fin des années 1970). Ces outils prennent la sortie exécutable d'un compilateur d'optimisation et l'optimisent encore plus. Les optimiseurs post-passage fonctionnent généralement au niveau du langage assembleur ou du code machine (contrairement aux compilateurs qui optimisent les représentations intermédiaires des programmes). Un tel exemple est le compilateur C portable (pcc) des années 1980, qui avait une passe facultative qui effectuait des post-optimisations sur le code assembleur généré.

Une autre considération est que les algorithmes d'optimisation sont compliqués et, en particulier lorsqu'ils sont utilisés pour compiler des langages de programmation volumineux et complexes, peuvent contenir des bogues qui introduisent des erreurs dans le code généré ou provoquent des erreurs internes lors de la compilation. Les erreurs du compilateur de toute nature peuvent être déconcertantes pour l'utilisateur, mais particulièrement dans ce cas, car il peut ne pas être clair que la logique d'optimisation est en cause. Dans le cas d'erreurs internes, le problème peut être partiellement résolu par une technique de programmation "à sécurité intégrée" dans laquelle la logique d'optimisation dans le compilateur est codée de telle sorte qu'un échec est piégé, un message d'avertissement émis et le reste de la compilation procède à la réussite.

Histoire

Les premiers compilateurs des années 1960 étaient souvent principalement concernés par la simple compilation de code correctement ou efficacement, de sorte que les temps de compilation étaient une préoccupation majeure. L'un des premiers compilateurs d'optimisation notables était le compilateur IBM FORTRAN H de la fin des années 1960. Un autre des compilateurs d'optimisation les plus anciens et les plus importants, qui a été le pionnier de plusieurs techniques avancées, était celui de BLISS (1970), qui a été décrit dans The Design of an Optimizing Compiler (1975). À la fin des années 1980, l'optimisation des compilateurs était suffisamment efficace pour que la programmation en langage assembleur décline. Cela a co-évolué avec le développement de puces RISC et de fonctionnalités de processeur avancées telles que la planification d'instructions et l'exécution spéculative, qui ont été conçues pour être ciblées par l'optimisation des compilateurs plutôt que par du code d'assemblage écrit par l'homme.

Liste des analyses de code statique

Voir également

Les références

Liens externes