Conception du compilateur - Optimisation du code

L'optimisation est une technique de transformation de programme, qui tente d'améliorer le code en le faisant consommer moins de ressources (c.-à-d. CPU, mémoire) et fournir une vitesse élevée.

Dans l'optimisation, les constructions de programmation générale de haut niveau sont remplacées par des codes de programmation de bas niveau très efficaces. Un processus d'optimisation de code doit suivre les trois règles ci-dessous:

Le code de sortie ne doit en aucun cas changer la signification du programme.
L'optimisation devrait augmenter la vitesse du programme et si possible, le programme devrait exiger moins de ressources.
L'optimisation doit elle-même être rapide et ne doit pas retarder le processus de compilation global.

Des efforts pour un code optimisé peuvent être faits à différents niveaux de compilation du processus.

Au début, les utilisateurs peuvent modifier / réorganiser le code ou utiliser de meilleurs algorithmes pour écrire le code.
Après avoir généré du code intermédiaire, le compilateur peut modifier le code intermédiaire par des calculs d'adresses et des boucles améliorées.
Lors de la production du code machine cible, le compilateur peut utiliser la hiérarchie de la mémoire et les registres CPU.

L'optimisation peut être classée en deux grandes catégories: indépendante de la machine et dépendante de la machine.

Optimisation indépendante de la machine

Dans cette optimisation, le compilateur prend le code intermédiaire et transforme une partie du code qui n'implique aucun registre CPU et / ou emplacement mémoire absolu. Par exemple:

do
{
   item = 10;
   value = value + item; 
} while(value<100);

Ce code implique une affectation répétée de l'élément identifiant, qui si nous mettons de cette façon:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

devrait non seulement enregistrer les cycles du processeur, mais peut être utilisé sur n'importe quel processeur.

Optimisation en fonction de la machine

L'optimisation dépendante de la machine est effectuée une fois que le code cible a été généré et lorsque le code est transformé en fonction de l'architecture de la machine cible. Il implique des registres CPU et peut avoir des références de mémoire absolues plutôt que des références relatives. Les optimiseurs dépendant de la machine s'efforcent de tirer le meilleur parti de la hiérarchie de la mémoire.

Blocs de base

Les codes sources ont généralement un certain nombre d'instructions, qui sont toujours exécutées en séquence et sont considérées comme les blocs de base du code. Ces blocs de base n'ont pas d'instruction de saut parmi eux, c'est-à-dire que lorsque la première instruction est exécutée, toutes les instructions d'un même bloc de base seront exécutées dans leur séquence d'apparition sans perdre le contrôle de flux du programme.

Un programme peut avoir diverses constructions en tant que blocs de base, comme des instructions conditionnelles IF-THEN-ELSE, SWITCH-CASE et des boucles telles que DO-WHILE, FOR et REPEAT-UNTIL, etc.

Identification de bloc de base

Nous pouvons utiliser l'algorithme suivant pour trouver les blocs de base dans un programme:

Rechercher les instructions d'en-tête de tous les blocs de base à partir desquels un bloc de base commence:
- Premier énoncé d'un programme.
- Les instructions qui sont la cible de n'importe quelle branche (conditionnelle / inconditionnelle).
- Déclarations qui suivent toute instruction de branche.
Les instructions d'en-tête et les instructions qui les suivent forment un bloc de base.
Un bloc de base n'inclut aucune instruction d'en-tête d'aucun autre bloc de base.

Les blocs de base sont des concepts importants du point de vue de la génération de code et de l'optimisation.

Les blocs de base jouent un rôle important dans l'identification des variables, qui sont utilisées plus d'une fois dans un seul bloc de base. Si une variable est utilisée plus d'une fois, la mémoire de registre allouée à cette variable n'a pas besoin d'être vidée à moins que le bloc ne termine l'exécution.

Graphique de flux de contrôle

Les blocs de base d'un programme peuvent être représentés au moyen de graphiques de flux de contrôle. Un graphique de flux de contrôle décrit la manière dont le contrôle du programme est transmis entre les blocs. C'est un outil utile qui aide à l'optimisation en aidant à localiser les boucles indésirables dans le programme.

Optimisation des boucles

La plupart des programmes s'exécutent en boucle dans le système. Il devient nécessaire d'optimiser les boucles pour économiser les cycles CPU et la mémoire. Les boucles peuvent être optimisées par les techniques suivantes:

Invariant code: Un fragment de code qui réside dans la boucle et calcule la même valeur à chaque itération est appelé un code invariant de boucle. Ce code peut être déplacé hors de la boucle en l'enregistrant pour être calculé une seule fois, plutôt qu'à chaque itération.
Induction analysis : Une variable est appelée variable d'induction si sa valeur est modifiée dans la boucle par une valeur invariante de boucle.
Strength reduction: Il existe des expressions qui consomment plus de cycles CPU, de temps et de mémoire. Ces expressions doivent être remplacées par des expressions moins chères sans compromettre la sortie de l'expression. Par exemple, la multiplication (x * 2) est chère en termes de cycles CPU que (x << 1) et donne le même résultat.

Élimination du code mort

Le code mort est une ou plusieurs instructions de code, qui sont:

Soit jamais exécuté, soit inaccessible,
Ou s'ils sont exécutés, leur sortie n'est jamais utilisée.

Ainsi, le code mort ne joue aucun rôle dans aucune opération du programme et peut donc être simplement éliminé.

Code partiellement mort

Il existe des instructions de code dont les valeurs calculées ne sont utilisées que dans certaines circonstances, c'est-à-dire que parfois les valeurs sont utilisées et parfois elles ne le sont pas. Ces codes sont connus sous le nom de code mort partiel.

Le graphique de flux de contrôle ci-dessus représente un morceau de programme où la variable «a» est utilisée pour affecter la sortie de l'expression «x * y». Supposons que la valeur assignée à 'a' ne soit jamais utilisée à l'intérieur de la boucle. Immédiatement après que le contrôle ait quitté la boucle, 'a' se voit attribuer la valeur de la variable 'z', qui sera utilisée plus tard dans le programme. Nous concluons ici que le code d'affectation de «a» n'est jamais utilisé nulle part, il est donc éligible pour être éliminé.

De même, l'image ci-dessus montre que l'instruction conditionnelle est toujours fausse, ce qui implique que le code, écrit en cas vrai, ne sera jamais exécuté, par conséquent, il peut être supprimé.

Redondance partielle

Les expressions redondantes sont calculées plus d'une fois dans un chemin parallèle, sans aucune modification des opérandes, alors que les expressions partiellement redondantes sont calculées plus d'une fois dans un chemin, sans aucun changement d'opérandes. Par exemple,

[expression redondante]	[expression partiellement redondante]

Le code invariant en boucle est partiellement redondant et peut être éliminé en utilisant une technique de mouvement de code.

Un autre exemple de code partiellement redondant peut être:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Nous supposons que les valeurs des opérandes (y et z) ne sont pas modifiés depuis l'affectation de la variable a à variable c. Ici, si l'instruction de condition est vraie, alors y OP z est calculé deux fois, sinon une fois. Le mouvement de code peut être utilisé pour éliminer cette redondance, comme indiqué ci-dessous:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Ici, si la condition est vraie ou fausse; y OP z ne doit être calculé qu'une seule fois.