Optimisation du compilateur

Un compilateur optimisant est un compilateur conçu pour générer du code optimisé dans des aspects tels que la minimisation du temps d'exécution du programme, l'utilisation de la mémoire , la taille de stockage et la consommation d'énergie. L'optimisation est généralement implémentée sous la forme d'une séquence de transformations d'optimisation , d'algorithmes qui transforment le code pour produire un code sémantiquement équivalent optimisé pour certains aspects. Il est généralement gourmand en CPU et en mémoire . En pratique, des facteurs tels que la mémoire disponible et la volonté d'un programmeur d'attendre la compilation limitent les optimisations qu'un compilateur peut fournir. Les recherches indiquent que certains problèmes d'optimisation sont NP-complets , voire indécidables .

En général, l'optimisation ne peut pas produire un résultat optimal , ce qui est impossible dans un sens général puisque l'optimisation d'un aspect peut dégrader les performances d'un autre. Les optimisations sont plutôt des méthodes heuristiques pour améliorer l'utilisation des ressources dans les programmes classiques.

Les optimisations sont classées de différentes manières qui se chevauchent.

La portée décrit la quantité de code d'entrée considérée pour appliquer des optimisations.

Les optimisations de portée locale utilisent des informations locales à un bloc de base . Étant donné que les blocs de base ne contiennent aucune instruction de flux de contrôle, ces optimisations nécessitent une analyse minimale, ce qui réduit les besoins en temps et en stockage. Cependant, aucune information n'est conservée entre les sauts.

Les optimisations de portée globale, également appelées optimisations intra-procédurales , fonctionnent sur des fonctions individuelles. Cela leur donne plus d'informations sur lesquelles travailler, mais nécessite souvent des calculs coûteux. Des hypothèses du pire des cas doivent être formulées lorsque des appels de fonction se produisent ou que des variables globales sont consultées, car peu d'informations sont disponibles à leur sujet.

Les optimisations par judas sont généralement effectuées tard dans le processus de compilation, après la génération du code machine . Cette optimisation examine quelques instructions adjacentes (comme si on « regardait à 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 deux peut être exécutée plus efficacement en décalant la valeur vers la gauche ou en ajoutant la valeur à elle-même (cet exemple est également une instance de réduction de la force ).

Les optimisations interprocédurales analysent l'ensemble du code source d'un programme. Plus les informations disponibles sont nombreuses, plus les optimisations peuvent être efficaces. Les informations peuvent être utilisées pour diverses optimisations, notamment l'intégration de fonctions , où un appel à une fonction est remplacé par une copie du corps de la fonction.

L'optimisation au moment de la liaison (LTO), ou optimisation de programme complet, est une classe plus générale d'optimisation interprocédurale. Pendant LTO, le compilateur a une visibilité sur les unités de traduction, ce qui lui permet d'effectuer des optimisations plus agressives comme l'intégration inter-modules et la dévirtualisation .

L'optimisation du code machine utilise un optimiseur de code objet pour analyser l'image de la tâche exécutable du programme après que tout le code machine exécutable a été lié . Certaines des techniques qui peuvent être appliquées dans une portée plus limitée, comme la compression de macros qui économise de l'espace en regroupant les séquences d'instructions communes, sont plus efficaces lorsque l'image complète de la tâche exécutable est disponible pour l'analyse.

La plupart des langages de programmation de haut niveau partagent des constructions et des abstractions de programmation communes : ramification (if, switch), boucle (for, while) et encapsulation (structures, objets). Ainsi, des techniques d'optimisation similaires peuvent être utilisées dans tous les langages. Cependant, certaines fonctionnalités du langage rendent certaines optimisations difficiles. Par exemple, les pointeurs en C et C++ rendent l'optimisation des tableaux difficile (voir analyse des alias ). Cependant, des langages tels que PL/I qui prennent également en charge les pointeurs ont des optimisations pour les tableaux. Inversement, certaines fonctionnalités du langage facilitent certaines optimisations. Par exemple, dans certains langages, 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 en déduire que le résultat de la fonction ne doit être calculé qu'une seule fois. Dans les langages où les fonctions sont autorisées à avoir des effets secondaires, le compilateur peut restreindre cette optimisation aux fonctions dont il peut déterminer qu'elles n'ont pas d'effets secondaires.

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 la plupart des optimisations les plus efficaces sont celles qui exploitent au mieux les fonctionnalités spéciales de la plate-forme cible. Les exemples sont les instructions qui font plusieurs choses à la fois, comme décrémenter un registre et créer une branche si ce n'est pas zéro.

Voici un exemple d'optimisation locale dépendante de la machine. Pour définir un registre à 0, la méthode la plus évidente consiste à utiliser la constante « 0 » dans une instruction qui définit une valeur de registre à une constante. Une méthode moins évidente consiste à effectuer un XOR entre un registre et lui-même. Il appartient au compilateur de savoir quelle variante d'instruction utiliser. Sur de nombreuses machines RISC , les deux instructions seraient tout aussi appropriées, car elles auraient toutes 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 cela est que le 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 un XOR d'un registre avec lui-même comme cas particulier qui ne provoque pas de blocage.

Machine cible

La possibilité et la nécessité d'appliquer des optimisations particulières 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 qu'ils puissent être utilisés pour optimiser différentes machines.

Architecture du processeur cible

• Nombre de registres : Les registres peuvent être utilisés pour optimiser les performances. Les variables locales peuvent être stockées dans des registres plutôt que dans la pile . Les résultats temporaires/intermédiaires peuvent être consultés dans des registres plutôt que dans une mémoire plus lente.

• 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 durées différentes. Les jeux d'instructions RISC tentent de limiter la variabilité de chacun de ces éléments : 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 (le nombre d'instructions terminées par période de temps, généralement un multiple entier du cycle d'horloge) est généralement constant 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 d'assemblage . Il permet l'utilisation de parties du processeur pour différentes instructions en divisant l'exécution des instructions en plusieurs étapes : décodage d'instruction, décodage d'adresse, extraction de mémoire, extraction de registre, calcul, stockage de registre, etc. Une instruction peut être dans l'étape de stockage de registre, tandis qu'une autre peut être dans l'étape 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 qui la précède dans le pipeline mais qui n'est pas encore terminée. Les conflits de pipeline peuvent conduire à des blocages de pipeline : où le processeur perd des cycles à attendre 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 : certains processeurs disposent de plusieurs ALU et FPU qui leur permettent d'exécuter plusieurs instructions simultanément. Il peut y avoir des restrictions sur les instructions qui peuvent être couplées avec d'autres instructions (le « couplage » correspond à l'exécution simultanée de deux instructions ou plus) et sur l'unité fonctionnelle qui peut exécuter quelle instruction. Ils présentent également des problèmes similaires aux conflits de pipeline. Les instructions peuvent être planifiées de manière à ce que les unités fonctionnelles soient entièrement chargées.

Architecture de la machine

• Taille et type de cache du processeur (mappage direct, 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 plus de risques de collisions de cache, même dans un cache non rempli.

• Taux de transfert du cache/de la mémoire : ils donnent au compilateur une indication de la pénalité pour les échecs de cache. Ceci est principalement utilisé dans les applications spécialisées.

Utilisation prévue

• Débogage : pendant le développement, les optimisations sont souvent désactivées pour accélérer la compilation ou pour faciliter le débogage du code exécutable. Les transformations d'optimisation, en particulier celles qui réorganisent le code, peuvent rendre difficile la mise en relation du code exécutable avec le code source.

• Utilisation à usage général : les logiciels pré-packagés sont souvent censés s'exécuter sur une variété de machines qui peuvent partager le même jeu d'instructions, mais qui ont des caractéristiques de performances différentes. Le code peut ne pas être optimisé pour une machine particulière, ou peut être réglé pour fonctionner de manière optimale sur la machine la plus populaire tout en fonctionnant de manière moins optimale sur d'autres.

• Utilisation à des fins spéciales : si le logiciel est compilé pour des machines ayant des caractéristiques uniformes, le compilateur peut alors optimiser considérablement le code généré pour ces machines.

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

Le micrologiciel 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 être plus importants que la vitesse du code. Par exemple, les compilateurs pour logiciels embarqués proposent généralement des options qui réduisent la taille du code au détriment de la vitesse. Le timing du code peut devoir être prévisible, plutôt que le plus rapide possible, de sorte que la mise en cache du code peut être désactivée, ainsi que les optimisations du compilateur qui l'exigent.

L’optimisation comprend les thèmes suivants, parfois contradictoires.

Optimiser le cas commun

Le cas le plus courant peut avoir des propriétés uniques qui permettent un chemin rapide au détriment d'un chemin lent . Si le chemin rapide est emprunté le plus souvent, le résultat est une meilleure performance globale.

É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 se traduit généralement par une exécution plus rapide. Par ailleurs, dans les systèmes embarqués , moins de code entraîne un coût de produit inférieur.

Moins de sauts grâce à l'utilisation du 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 ramifications, 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 à un moment proche doivent être placés à proximité les uns des autres en 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 à chaque niveau de la hiérarchie de la mémoire , il faut donc placer d'abord les éléments les plus couramment utilisés dans les registres, puis dans les caches, puis dans la mémoire principale, avant d'aller sur le disque.

Paralléliser

Réorganiser les opérations pour permettre à plusieurs calculs de se produire en parallèle, soit au niveau de l'instruction, de la mémoire ou du thread.

Des informations plus précises sont meilleures

Plus les informations dont dispose le compilateur sont précises, mieux il peut utiliser une ou plusieurs de ces techniques d’optimisation.

Les mesures d'exécution peuvent aider

Les informations recueillies lors d'un test peuvent être utilisées dans le cadre d' une 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 l'optimisation de manière dynamique.

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 la multiplication par son inverse, ou utilisez l'analyse des variables par induction pour remplacer la multiplication par un indice de boucle par l'addition.

L'optimisation des boucles agit sur les instructions qui composent une boucle, comme une boucle for , par exemple un code invariant en boucle . Les optimisations de boucle peuvent avoir un impact significatif car de nombreux programmes passent un pourcentage important de leur temps à l'intérieur des boucles.

Certaines techniques d’optimisation principalement conçues pour fonctionner sur des boucles incluent :

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 la force et elle peut également permettre aux définitions de la variable d'index de devenir du code mort . Ces informations sont également utiles pour l'élimination des vérifications de limites et l'analyse des dépendances , entre autres.

Fission de boucle ou distribution de boucle

La fission de boucle tente de diviser une boucle en plusieurs boucles sur la même plage d'index, chaque nouvelle boucle n'occupant qu'une partie du corps de la boucle d'origine. Cela peut améliorer la localité de référence à la fois aux données auxquelles on accède dans la boucle et au code dans le corps de la boucle.

Fusion de boucles ou combinaison de boucles ou enfoncement de boucles ou brouillage de boucles

Une autre technique qui tente de réduire la surcharge de boucle. Lorsque deux boucles adjacentes doivent effectuer le même nombre d'itérations, 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 appelée 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 de la condition (augmente 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 protection if peut être ignorée.

Échangeur de boucle

Ces optimisations échangent des boucles internes avec des boucles externes. Lorsque les variables de boucle sont indexées dans un tableau, une telle transformation peut améliorer la localité de référence, en fonction de 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 pour chaque itération, il peut être considérablement plus efficace de la hisser en dehors 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 dehors de la boucle en toute sécurité.

Optimisation des imbrications de boucles

Certains algorithmes répandus, comme la multiplication de matrices, ont un comportement de cache très médiocre et des accès à la mémoire excessifs. L'optimisation par imbrication de boucles augmente le nombre de hits de cache en opérant 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 attribué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 d'exécution sorte de 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 nécessite le nombre à comparer. Par conséquent, la quantité d'octets nécessaire pour stocker le paramètre est économisée 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 doivent être exécutées pour é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 diminuer le nombre de fois où la condition de boucle est testée et le nombre de sauts ; les tests et les sauts peuvent nuire aux performances en altérant le pipeline d'instructions. Une optimisation avec « 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.

Séparation 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 les mêmes corps mais qui itèrent sur différentes parties contiguës de la plage d'index. Un cas particulier utile est le peeling 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.

Boucle de désactivation

La désactivation déplace une condition 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 de la condition.

Pipeline logiciel

La boucle est restructurée de telle manière que le travail effectué dans une itération est 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) pour utiliser plusieurs processeurs simultanément dans une machine multiprocesseur à mémoire partagée (SMP), y compris les machines multicœurs.

Les optimisations de stockage prémonitoires 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éarrangements de code qui préservent la sémantique des programmes correctement synchronisés.

Les optimisations de flux de données , basées sur l'analyse de flux de données , dépendent principalement de la manière dont certaines propriétés des données sont propagées par les arêtes de contrôle dans le graphe de flux de contrôle . En voici quelques exemples :

Élimination des sous-expressions courantes

Dans l'expression (a + b) - (a + b)/4, « sous-expression commune » fait référence à la duplication (a + b). Les compilateurs qui implémentent cette technique réalisent que cela (a + b)ne changera pas et ne calculent donc sa valeur qu'une seule fois.

Pliage et propagation constants

remplacement des 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 langages modernes.

Reconnaissance et élimination des variables d'induction

voir la discussion ci-dessus sur l'analyse des variables d'induction .

Classification des alias et analyse des pointeurs

En présence de pointeurs , il est difficile de procéder à des optimisations, car potentiellement, n'importe quelle variable peut avoir été modifiée lors de l'affectation d'un emplacement mémoire. En spécifiant quels pointeurs peuvent créer des alias pour quelles variables, les pointeurs non liés peuvent être ignorés.

Élimination des stocks morts

suppression des affectations aux variables qui ne sont pas lues ultérieurement, soit parce que la durée de vie de la variable se termine, soit en raison d'une affectation ultérieure qui écrasera la première valeur.

Ces optimisations sont destinées à être effectuées après la transformation du programme en une forme spéciale appelée affectation unique statique , dans laquelle chaque variable est affectée à un seul endroit. Bien que certaines fonctionnent sans SSA, elles sont plus efficaces avec SSA. De nombreuses optimisations répertoriées dans d'autres sections bénéficient également de modifications 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 peut identifier certaines redondances que l'élimination des sous-expressions communes ne peut pas, et vice versa.

Propagation conditionnelle de constantes clairsemées

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, propageant simultanément des valeurs constantes et éliminant des parties du graphique de flux de contrôle que cela rend inaccessibles.

Attribution des registres

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 les 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 de valeurs qui se croisent), elles ont une arête entre elles. Ce graphique est coloré en utilisant par exemple l'algorithme de Chaitin en utilisant le même nombre de couleurs qu'il y a de registres. Si la coloration échoue, une variable est « renversée » en mémoire et la coloration est relancée.

Sélection des instructions

La plupart des architectures, en particulier les architectures CISC et celles qui comportent de nombreux modes d'adressage , offrent plusieurs façons différentes d'effectuer une opération particulière, en utilisant des séquences d'instructions entièrement différentes. Le rôle du sélecteur d'instructions est de faire du bon travail dans l'ensemble en choisissant les instructions avec lesquelles implémenter les opérateurs dans la représentation intermédiaire de bas niveau . Par exemple, sur de nombreux processeurs de la famille 68000 et de l'architecture x86, des modes d'adressage complexes peuvent être utilisés dans des instructions telles que lea 25(a1,d5*4), a0, ce qui permet à une seule instruction d'effectuer une quantité importante d'arithmétique avec moins de stockage.

Planification des cours

La planification des instructions est une optimisation importante pour les processeurs pipeline 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, éliminant ainsi un accès à la mémoire. Cette opération est effectuée en tandem avec l'allocation de registres pour éviter les débordements.

Factorisation de code

Si plusieurs séquences de code sont identiques, ou peuvent être paramétrées ou réorganisées pour être identiques, elles peuvent être remplacées par des appels à une sous-routine partagée. Cela permet souvent de partager du code pour la configuration de la sous-routine et parfois la récursivité terminale.

Trampolines

De nombreux processeurs ont des instructions d'appel de sous-programme plus petites pour accéder à la mémoire faible. 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 localité des données et exposent davantage de parallélisme en réorganisant les calculs. Les compilateurs optimisant l'espace peuvent réorganiser le code pour allonger les séquences qui peuvent être factorisées en sous-routines.

Bien que beaucoup d’entre elles s’appliquent également aux langages non fonctionnels, elles sont issues de langages fonctionnels tels que Lisp et ML ou y sont particulièrement critiques .

Optimisation des appels de queue

Un appel de fonction consomme de l'espace sur la pile et implique une surcharge liée au passage des paramètres et au vidage du cache d'instructions. Les algorithmes récursifs de fin peuvent être convertis en itération via un processus appelé élimination de la récursivité de fin ou optimisation des appels de fin.

Déforestation ( fusion de structures de données )

Dans les langages où il est courant d'appliquer une séquence de transformations à une liste, la déforestation tente de supprimer la construction de structures de données intermédiaires.

Évaluation partielle

Élimination des limites

De nombreux langages, comme Java , imposent la vérification des limites de tous les accès aux tableaux. Il s'agit d'un sérieux 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 variable de boucle simple.

Optimisation du décalage des branches (en fonction de 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 d'un programme pour réduire les branches conditionnelles et améliorer la localité de référence.

Élimination du code mort

Supprime les instructions qui n'affectent 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 lorsqu'elle ne l'est pas, elle peut être écrite une seule fois en dehors de l'instruction conditionnelle. De même, si certains types d'expressions (par exemple, l'affectation d'une constante à une variable) apparaissent à l'intérieur d'une boucle, elles peuvent en être retirées car leur effet sera le même, qu'elles soient exécutées plusieurs fois ou une seule fois. C'est ce qu'on appelle également l'é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 appelle une procédure , il est possible d'insérer directement le corps de la procédure dans le code appelant plutôt que de lui transférer le contrôle. Cela permet d'économiser la surcharge liée aux appels de procédure, ainsi que de fournir la possibilité de nombreuses optimisations spécifiques aux paramètres, mais se fait 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 général, l'inlining 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 instructions 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 l'inlining de code.

Saut de filetage

Dans cette optimisation, les sauts conditionnels consécutifs prédiqué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 macro

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 conserver 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 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éorganisation des tests

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 dépendent pas l'un de l'autre. La sémantique de court-circuit peut rendre cela difficile.

L'optimisation interprocédurale fonctionne sur l'ensemble du programme, au-delà des limites des procédures et des fichiers. Elle fonctionne en étroite collaboration avec ses homologues intraprocédurales, réalisées avec la coopération d'une partie locale et d'une partie globale. Les optimisations interprocédurales typiques sont l'intégration de procédures , l'élimination de code mort interprocédural, la propagation de constantes interprocédurales 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 des alias, l'analyse de l'accès aux tableaux 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 compilateur open source GCC a été critiqué pour son manque d'analyse et d'optimisation interprocédurales puissantes, bien que cela s'améliore maintenant. Un autre compilateur open source avec une infrastructure d'analyse et d'optimisation complète 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 les options du compilateur de manière explicite pour indiquer au compilateur d'activer l'analyse interprocédurale et d'autres optimisations coûteuses.

Il peut y avoir une large gamme d'optimisations qu'un compilateur peut effectuer, allant des optimisations simples et directes qui prennent peu de temps de compilation aux optimisations é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 de contrôle ou à leur procédure pour permettre à l'utilisateur du compilateur de choisir le niveau d'optimisation à demander ; 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 pour les compilateurs, tels que Clang , d'avoir plusieurs options de commande de compilateur qui pouvaient affecter une variété de choix d'optimisation, à commencer par le commutateur familier -O2.

Une approche pour isoler l'optimisation consiste à utiliser ce que l'on appelle des optimiseurs 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-pass 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é.

Un autre point à prendre en compte 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 de compilation de toute sorte peuvent être déconcertantes pour l'utilisateur, mais c'est particulièrement le cas dans ce cas, car il peut ne pas être évident que la logique d'optimisation soit en cause. Dans le cas d'erreurs internes, le problème peut être partiellement atténué par une technique de programmation « à sécurité intégrée » dans laquelle la logique d'optimisation du compilateur est codée de telle sorte qu'une défaillance est détectée, qu'un message d'avertissement est émis et que le reste de la compilation se déroule jusqu'à son terme.

Les premiers compilateurs des années 1960 se préoccupaient principalement de compiler le 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 premiers et des plus importants compilateurs d'optimisation, 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, les compilateurs d'optimisation étaient suffisamment efficaces pour que la programmation en langage assembleur décline. Cela a évolué avec le développement des puces RISC et des fonctionnalités avancées des processeurs telles que les processeurs superscalaires , l'exécution hors service et l'exécution spéculative , qui ont été conçues pour être ciblées par les compilateurs d'optimisation plutôt que par le code assembleur écrit par l'homme.

• Analyse des alias
• Analyse du pointeur
• Analyse de forme
• Analyse d'évasion
• Analyse d'accès au tableau
• Analyse de dépendance
• Analyse de contrôle des flux
• Analyse des flux de données
  • Analyse de la chaîne d'utilisation et de définition
  • Analyse des variables en direct
  • Analyse d'expression disponible