Conception du compilateur - Génération de code

La génération de code peut être considérée comme la phase finale de la compilation. Grâce à la génération de code postal, le processus d'optimisation peut être appliqué au code, mais cela peut être considéré comme faisant partie de la phase de génération de code elle-même. Le code généré par le compilateur est un code objet d'un langage de programmation de niveau inférieur, par exemple, le langage d'assemblage. Nous avons vu que le code source écrit dans un langage de niveau supérieur est transformé en un langage de niveau inférieur qui se traduit par un code objet de niveau inférieur, qui doit avoir les propriétés minimales suivantes:

  • Il doit porter la signification exacte du code source.
  • Il doit être efficace en termes d'utilisation du processeur et de gestion de la mémoire.

Nous allons maintenant voir comment le code intermédiaire est transformé en code objet cible (code assembleur, dans ce cas).

Graphe acyclique dirigé

Directed Acyclic Graph (DAG) est un outil qui décrit la structure des blocs de base, aide à voir le flux de valeurs circulant entre les blocs de base et offre également une optimisation. DAG permet une transformation facile sur des blocs de base. DAG peut être compris ici:

  • Les nœuds feuilles représentent des identifiants, des noms ou des constantes.

  • Les nœuds intérieurs représentent les opérateurs.

  • Les nœuds intérieurs représentent également les résultats des expressions ou les identifiants / nom où les valeurs doivent être stockées ou attribuées.

Example:

t0 = a + b
t1 = t0 + c
d = t0 + t1

[t 0 = a + b]

[t 1 = t 0 + c]

[d = t 0 + t 1 ]

Optimisation du judas

Cette technique d'optimisation fonctionne localement sur le code source pour le transformer en un code optimisé. Par localement, nous entendons une petite partie du bloc de code disponible. Ces méthodes peuvent être appliquées sur des codes intermédiaires ainsi que sur des codes cibles. Un groupe d'instructions est analysé et vérifié pour l'optimisation possible suivante:

Élimination des instructions redondantes

Au niveau du code source, les opérations suivantes peuvent être effectuées par l'utilisateur:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }
 
int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }
 
int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }
 
int add_ten(int x)
   {
   return x + 10;
   }

Au niveau de la compilation, le compilateur recherche des instructions de nature redondante. Le chargement et le stockage multiples d'instructions peuvent avoir la même signification même si certaines d'entre elles sont supprimées. Par exemple:

  • MOV x, R0
  • MOV R0, R1

Nous pouvons supprimer la première instruction et réécrire la phrase comme:

MOV x, R1

Code inaccessible

Le code inaccessible est une partie du code du programme qui n'est jamais accédée à cause des constructions de programmation. Les programmeurs peuvent avoir accidentellement écrit un morceau de code qui ne peut jamais être atteint.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

Dans ce segment de code, le printf l'instruction ne sera jamais exécutée lorsque le contrôle du programme revient avant de pouvoir s'exécuter, d'où printf Peut être enlevé.

Optimisation des flux de contrôle

Il existe des cas dans un code où le contrôle du programme saute d'avant en arrière sans effectuer aucune tâche significative. Ces sauts peuvent être supprimés. Considérez le morceau de code suivant:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

Dans ce code, l'étiquette L1 peut être supprimée lorsqu'elle passe le contrôle à L2. Ainsi, au lieu de sauter à L1 puis à L2, la commande peut directement atteindre L2, comme illustré ci-dessous:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Simplification de l'expression algébrique

Il y a des occasions où les expressions algébriques peuvent être simplifiées. Par exemple, l'expressiona = a + 0 peut être remplacé par a elle-même et l'expression a = a + 1 peut simplement être remplacée par INC a.

Réduction de la force

Il y a des opérations qui consomment plus de temps et d'espace. Leur «force» peut être réduite en les remplaçant par d'autres opérations qui consomment moins de temps et d'espace, mais produisent le même résultat.

Par exemple, x * 2 peut être remplacé par x << 1, qui n'implique qu'un seul décalage vers la gauche. Bien que la sortie d'un * a et d'un 2 soit la même, un 2 est beaucoup plus efficace à implémenter.

Accéder aux instructions de la machine

La machine cible peut déployer des instructions plus sophistiquées, qui peuvent avoir la capacité d'effectuer des opérations spécifiques de manière beaucoup plus efficace. Si le code cible peut accueillir ces instructions directement, cela améliorera non seulement la qualité du code, mais donnera également des résultats plus efficaces.

Générateur de code

Un générateur de code doit comprendre l'environnement d'exécution de la machine cible et son jeu d'instructions. Le générateur de code doit prendre en compte les éléments suivants pour générer le code:

  • Target language: Le générateur de code doit être conscient de la nature du langage cible pour lequel le code doit être transformé. Ce langage peut faciliter certaines instructions spécifiques à la machine pour aider le compilateur à générer le code d'une manière plus pratique. La machine cible peut avoir une architecture de processeur CISC ou RISC.

  • IR Type: La représentation intermédiaire a différentes formes. Il peut s'agir d'une structure AST (Abstract Syntax Tree), d'une notation polonaise inversée ou d'un code à 3 adresses.

  • Selection of instruction: Le générateur de code prend la représentation intermédiaire comme entrée et la convertit (mappe) dans le jeu d'instructions de la machine cible. Une représentation peut avoir de nombreuses façons (instructions) de la convertir, il incombe donc au générateur de code de choisir judicieusement les instructions appropriées.

  • Register allocation: Un programme a un certain nombre de valeurs à conserver pendant l'exécution. L'architecture de la machine cible peut ne pas permettre à toutes les valeurs d'être conservées dans la mémoire ou les registres du processeur. Le générateur de code décide des valeurs à conserver dans les registres. En outre, il décide des registres à utiliser pour conserver ces valeurs.

  • Ordering of instructions: Enfin, le générateur de code décide de l'ordre dans lequel l'instruction sera exécutée. Il crée des horaires pour les instructions pour les exécuter.

Descripteurs

Le générateur de code doit suivre à la fois les registres (pour la disponibilité) et les adresses (emplacement des valeurs) tout en générant le code. Pour les deux, les deux descripteurs suivants sont utilisés:

  • Register descriptor: Le descripteur de registre est utilisé pour informer le générateur de code de la disponibilité des registres. Le descripteur de registre garde une trace des valeurs stockées dans chaque registre. Chaque fois qu'un nouveau registre est requis pendant la génération de code, ce descripteur est consulté pour la disponibilité du registre.

  • Address descriptor: Les valeurs des noms (identificateurs) utilisés dans le programme peuvent être stockées à différents endroits lors de l'exécution. Les descripteurs d'adresses sont utilisés pour garder une trace des emplacements de mémoire où les valeurs des identificateurs sont stockées. Ces emplacements peuvent inclure des registres CPU, des tas, des piles, de la mémoire ou une combinaison des emplacements mentionnés.

Le générateur de code maintient à la fois le descripteur mis à jour en temps réel. Pour une instruction de chargement, LD R1, x, le générateur de code:

  • met à jour le descripteur de registre R1 qui a la valeur x et
  • met à jour le descripteur d'adresse (x) pour montrer qu'une instance de x est dans R1.

Génération de code

Les blocs de base se composent d'une séquence d'instructions à trois adresses. Le générateur de code prend cette séquence d'instructions comme entrée.

Note: Si la valeur d'un nom est trouvée à plus d'un endroit (registre, cache ou mémoire), la valeur du registre sera préférée au cache et à la mémoire principale. De même, la valeur du cache sera préférée à la mémoire principale. La mémoire principale n'a guère de préférence.

getReg: Le générateur de code utilise la fonction getReg pour déterminer l'état des registres disponibles et l'emplacement des valeurs de nom. getReg fonctionne comme suit:

  • Si la variable Y est déjà dans le registre R, elle utilise ce registre.

  • Sinon, si un registre R est disponible, il utilise ce registre.

  • Sinon, si les deux options ci-dessus ne sont pas possibles, il choisit un registre qui nécessite un nombre minimal d'instructions de chargement et de stockage.

Pour une instruction x = y OP z, le générateur de code peut effectuer les actions suivantes. Supposons que L est l'emplacement (de préférence le registre) où la sortie de y OP z doit être sauvegardée:

  • Appelez la fonction getReg, pour décider de l'emplacement de L.

  • Déterminez l'emplacement actuel (registre ou mémoire) de y en consultant le descripteur d'adresse de y. Siy n'est pas actuellement inscrit L, puis générez l'instruction suivante pour copier la valeur de y à L:

    MOV y ', L

    où y’ représente la valeur copiée de y.

  • Déterminez l'emplacement actuel de z en utilisant la même méthode utilisée à l'étape 2 pour y et générez l'instruction suivante:

    OP z ', L

    où z’ représente la valeur copiée de z.

  • Maintenant L contient la valeur de y OP z, qui est destinée à être affectée à x. Donc, si L est un registre, mettez à jour son descripteur pour indiquer qu'il contient la valeur dex. Mettre à jour le descripteur dex pour indiquer qu'il est stocké à l'emplacement L.

  • Si y et z n'ont plus aucune utilité, ils peuvent être restitués au système.

D'autres constructions de code telles que les boucles et les instructions conditionnelles sont transformées en langage d'assemblage de manière générale.