Génération de codeMathieu Lafourcade LIRMMversion du 16/03/2003 |
IntroductionNous aborderons la génération de code selon une approche fonctionelle. En effet, le générateur de code ayant besoin de la structure aborescente du programme, nous utiliserons à la place une forme équivalent préfixée (à la Lisp). La notion de schéma de compilation sera au cœur des transformations introduites. Un schéma de compilation est une règle de réécriture de la forme:
où <phrase1> est une énoncé du langage source et <phrase2> est une expression qui contient du code pour la machine cible. On notera les variables sous la forme <x> pour désigner une variable du schéma de compilation (qu'il faut bien évidemment différencier des variables du langage cible). L'opération de concaténation des expressions cibles s'exprimera à l'aide d'un point virgule ';'. L'opération de compilation est une opération récursive. On utilisera fortement le fait de passer les arguments sur la pile. On verra par la suite les problèmes d'optimisation que cela pose et on réfléchira à la manière de les régler. Notre pseudo-langage Lisp dispose d'arguments notés entre crochets [a1 ,a2,..., an]. L'opérateur @ dans la génération de code indique qu'il faut évaluer l'expression qui suit. La machine virtuelle - MVLa machine virtuelle que nous utilisons dispose d'une mémoire (fini, mais suffisement grande afin de ne pas être géné) et de trois registres R0, R1 et R2. La mémoire est un ensemble fini de N cellules. La première cellule a par définition le numéro 0, la dernière le numéro N-1. On parlera plutôt d'adresse mémoire que de numéro de cellule. La pile est gérée dans la mémoire. La pile commence à l'adresse indique dans le registre spécial BP (base pointer). A priori, on ne touchera jamais à ce registre. le sommet de pile est indiqué dans le registre spécial SP (stack pointer). La pile est vide quand SP = BP. On a toujours SP >= BP (la pile est montante). Le compteur de programme est contenu dans un registre spécial PC (program counter). Pour l'instant, nous avons donc les registres suivants : FP. Pour les comparaison et les sauts conditionnel, on dispose de trois registres booléens (1 bit) appelés drapeaux (flag) : DPP, DE, DPG (pour drapeau plus petit, drapeau égal, drapeau plus grand).
Modes d'adressageUn adressage correspond soit à un source <src> d'où est lue une valeur, soit à une destination <dest> où une valeur est écrite. Valeur constanteUne valeur constante s'écrit directement précédée par le symbole #. Par exemple :
Correspond à la valeur 50. une valeur constante ne peut être qu'une source (une telle destination n'aurait pas de sens). Mode directD'une façon générale, les instructions qui ont besoin d'accéder à des données vont indiquer comme paramètres l'endroit ou se trouvent ces données. Les registres sont directement indiqués tel quels. Par exemple :
S'il s'agit de sources <src>, ils correspondent respectivement à :
Les adresses sont indiquées directement. Par exemple :
correspond pour ue source à la valeur contenue dans l'adresse 500 : Mode indexéUne adresse calculée par addition d'un déplacement c au contenu d'une registre R, s'écrit sous la forme c(R). Ainsi, l'instruction:
correspond à la valeur contenue à l'adresse : Mode indirectLa forme indirecte est préfixée par *. Ainsi, l'instruction :
correspond à la valeur contenue à l'adresse
qui correspond à la valeur contenue à l'adresse contenue à l'adresse 500 c'est-à-dire Mode indirect indexéIl s'agit de la forme indirecte du mode indexée. Ainsi, l'instruction:
correspond à la valeur contenue à l'adresse Etiquettes et variables globalesCe type symbole est inséré dans le code pour référencer un adresse particulière. On suppose que la machine virtuelle dispose d'une table <étiquette, adresse> qui permet de retrouver l'adresse correspondant à une étiquette donnée. En précédant une étiquette par le caractère @, on fait référence à son adresse. Par exemple :
correspond à l'adresse ou se trouve l'étiquette D'une façon similaire, les variables globales sont référencées comme des étiquettes. Il s'agit d'étiquettes qui se trouvent à un endroit définis à l'avance dans la mémoire. Par exemple, les variables peuvent commencer à l'adresse 0. Par exemple, nous avons les variables globales A, B et C :
On a donc :
InstructionsLes instructions ont soit 0, 1 ou 2 paramètres. Sauf indication contraire tous les modes d'adressage sont possibles. En général, il s'agit de la source Instructions de base
Par exemple :
Par exemple :
Avec ces instructions, nous sommes capables d'écrire les instructions de pile. Toutefois, celles-ci peuvent raisonnablement être implémenté directement (code plus effiace et surtout plus clair). Instructions de pile
Instructions de saut
Instructions diverses
Schémas de compilationExpressions constantesLes expressions constantes seront empilées en plaçant les valeurs intermédiaires sur la pile en transformant les expressions sous une forme préfixée.
On supposera que les résultats de toutes les opérations sont passées dans le registre La compilation d'un opérateur primitif passe généralement par l'appel à une bibliothèque de primitives (calculs de flottants, calculs d'entiers longs, ...) par l'intermédiaire de l'instruction d'appel
Afin que ce mécanisme fontionne, il faut précéder chaque procédure (ou fonction) par un en-tête contenant son étiquette. Si
Ce code remplace l'appel En fait, dans le cas de Lisp on ne sait pas si l'opérateur est effectivement primitif ou non car on ne connaît pas le type des expressions. Cela changera avec l'introduction des types et donc on doit compiler les primitives en faisant appel à une bibliothèque de procédures primitives. Les constantes sont directement placées dans le registre
Les variables globales sont traitées par utilisation de l'accès direct à une case mémoire :
Exemple : Compiler l'expressions suivante:
Si on remet tout ça dans l'ordre on obtient :
Lorsqu'on ne fait pas appel à des sous-programmes et qu'on compile les appels à +, - et * directement dans la machine, cela donne :
Fonctions de testsEn général, les procédures de tests se compilent comme les opérateurs arithmétiques (sauf quand les tests peuvent être effectués par la machine cible et qu'ils se situent dans une structure de contrôle telle qu'un 'if'). Exemple : (a > 4)
Soit :
Les fonction booléennes retournent 0 (faux) ou 1 (vrai) comme valeurs. Affectation de variables globalesEn général, les procédures de tests se compilent comme les opérateurs arithmétiques (sauf quand les tests peuvent être effectués par la machine cible et qu'ils se situent dans une structure de contrôle telle qu'un 'if').
Par exemple, nous avons pour
L'état de la mémoire après exécution est :
Note : le code précédent qui pourrait s'optimiser :
Mais, une telle optimisation n'est immédiatement possible, si on a
Structures de contrôlesSéquenceLa structure de séquence s'exprime simplement comme la concaténation de la compilation des instructions se situant dans la séquence.
Si alors sinonLes structures de contrôles classiques (conditionnelles et boucles) doivent gérer des étiquettes.
Par exemple :
Boucle "tant que"Le 'tant que' utilise une technique semblable.
Par exemple :
Boucle "pour"Le 'pour' u est plus complexe Cas 1 :
Par exemple :
Cas 2 :
Par exemple :
FonctionsLes fonctions se trouvent à deux endroits :
Compilation d’une déclaration d'une fonctionPour l’instant on compile les fonctions sans paramètres ni variables locales. Une déclaration d’un sous-programme s’exprime ainsi :
où
Compilation d’un appel de sous-programmeL’appel d’un sous-programme s’exprime ainsi :
Remarque : cela montre la simplicité de la définition des sous-programmes. En fait le problème principal se situe non pas dans les sous-programmes, mais dans les variables locales et les paramètres passés en argument. Paramètres et variables localesDe nombreuses techniques peuvent être utilisées pour traiter les paramètres des procédures. La première, qui est celle employée initialement par Fortran, consiste à réserver des variables globales dans chaque procédure. Mais elle ne permet pas la récursivité. Les autres utilisent la pile. Passage de paramètres à la FortranDéclaration d'un sous-programme :
Appel d'un sous-programme :
Problèmes
Par exemple pour (1), considérons le code Lisp suivant :
Réponse : pour le problème (2), on peut utiliser un environnement. Un environnement est une suite de couples (symbole, valeur), que l’on notera
On ajoutera donc un argument à la fonction Ainsi, la compilation d’expression s’écrit maintenant ainsi :
Par exemple : ?
Lors de la compilation du corps d’une procédure, nous allons passer à la fois les noms des variables ainsi que les adresses (les étiquettes) des variables locales :
Par exemple :
Accès aux variables localesLors de la compilation des variables, ce qui s’exprimait auparavant ainsi :
se compile maintenant à l’aide des environnements :
Exemple :
Valeur de retourOn notera qu’il n’y a strictement rien à faire pour que les procédures retournent un résultat. Le dernier résultat se trouve dans R0 lors de la sortie de la procédure. Si l’on désire avoir une instruction de type
Passages de paramètres par la pile On utilise la pile pour le passage de paramètres. Le principe consiste à laisser les variables sur la pile. On obtient alors :
L’appel de procédure se fait simplement comme dans l’appel de type Fortran. Problème : comment accéder aux variables locales sur la pile ? Réponse : il faut marquer la pile lors de l’appel des sous-programmes. Il s'agit de la notion de bloc de pile (stack frame). on remarquera que ce n'est pas la seule solution possible, mais c'est une des plus simples et qui donne un code généré les plus lisibles. Il existe de nombreuses formes de bloc de pile, mais elles se ramenent simplement à faire des variantes de celle qui est décrite ci-dessous.
Cela signifie que lors de la compilation d’un appel il faut générer le code suivant :
On récupère les variables sur la pile à l’adresse suivante :
On peut utiliser avec profit l’instruction (local <n> <reg>) qui va chercher le nième élément sur la pile à partir de FP et le place dans le registre <reg>. Ainsi la compilation d’une procédure avec passage de paramètres se compile ainsi: Compile[(define (<proc> <x1> .. <xn>) <expr>),<env>] -->
Maintenant, l’accès aux variables s’écrit ainsi : Compile[<ident>,<env>] -->
De même l’affectation est donnée par : Compile[(setq <ident> <expr>), <expr>] -->
Compilation des variables locales Principe: les variables locales sont sur la pile et "poussent" à l'envers des paramètres. Ces variables sont introduites par le mot clé Var en Pascal au début d'une fonction où se situent au début d'un "bloc" en C. En Scheme et Lisp ces variables sont introduites par la structure let. On supposera que les variables locales sont définies une fois pour toute par le mot clé Remarque : On supposera qu'il n'est pas possible de définir (define (f x) On a donc le schémas suivant : Compile[(vars <x1> .. <xn>), <env>] -->
L'accès aux variables locales se fait ensuite comme pour les paramètres, c'est-à-dire par la règle de compilation suivante: Compile[<ident>,<env>] -->
Procédures dans des variables Certains compilateurs Pascal et C permettent d'avoir des pointeurs sur des procédures et d'utiliser dynamiquement ces procédures. Par exemple: void f(int x) {..} De même en Scheme on peut écrire: (define (f x y)(* x y)) Principe: si l'on s'aperçoit que l'identificateur réfère à une fonction (mais qu'elle n'a pas été définie ainsi), on compile non pas un appel direct, mais un appel indirect via Compile[(<expr> <e1> ... <en>), <env>] -->
Remarque: cette modification peut s'appliquer aussi à l'appel direct. C'est généralement ce qui se passe dans les langages faiblement typés, où il est difficile de savoir si la variable est un identificateur correspondant effectivement à la fonction où s'il s'agit d'une variable qui contient une procédure. Fonctions auxilliaires (labels)Compilation des fonctions auxiliaires que l'on ne veut pas définir à l'extérieur d'une procédure. On rencontre ce type de procédure en Pascal, en Ada et en Scheme. Exemple en Lisp: à faire (defun indice (lst x) ;; appel (indice '(a b c d e) 'c) --> 2 ;; (define (f x) (define (g z) (set! x (1+ z)) x) (+ x (g 3))) ;; appel (f 5 )--> 9 Principe:
La compilation des procédures les plus globales n'est pas modifiée. Voici la nouvelle compilation des procédures: Compile[(define (<proc> <x1> .. <xn>) <expr>),<env>] soit n = nombre de paramètres <nenv> = {{(<x1>,-(n+1)+1),.., --> <proc> // l’etiquette du sous-programme FENTRY <proc> // ne sert à rien en fait Compile[<expr>,<nenv>] RTN Le changement principal se situe dans l'accès aux variables: Compile[<ident>,<env>] --> Compile[<ident>,<env>] -->
Et voilà le code de recherche d'un élément dans les blocs de piles englobant : Compile[<ident>,<env>] --> MOVE (FP+1) R1 // on prend l'ancien FP (indirect indexé) recherche JEQ R2 trouve // R2 = 0 MOV (R1+1) R1 // recupere les FP DECF R2 // on decremente R2 JMP recherche trouve MOV FP R2 // on sauve FP MOVE R1 FP // FP prend la valeur du FP "global" LOCAL @var_x R0 // on met le resultat dans R0 MOV R2 FP // FP reprend sa valeur
C'est tout ! Structures de donnéesPour la compilation des structures de données, il existe plusieurs classes de données:
Tableaux et Compilation statique1. Déclaration On réserve de la place dans une zone de données. Var A : Array[1..6] of Integer; sera transformé en: A:word 0 On a donc: Compile[<nom> : Array [1..<n>] of Integer, <env>] et <env> = nil // environnement global --> <nom> word 0; for i = 1 to <n>-1 do word 0 2. Accès en lecture: Compile[<tab>[<expr>],<env>] --> Compile[<expr>, <env>]; MOVE R1 <tab>); // recupere l'adresse de base ADD R0 R1; // ajoute l'offset (MOV A0 (A1)); // recherche indirecte de l'information. 3. Accès en écriture: Compile[<tab>[<expr1>]:= <expr2>,<env>] --> Compile[<expr1>, <env>]; (PUSH A0) Compile[<expr2>, <env>]; (MOV A1 <tab>); // recupere l'adresse de base (POP A2);?// recupere la valeur de l'offset (MOV A1 A1 A2); // ajoute l'offset (MOV (A1) A0);?// sauvegarde indirecte
Tableaux et Compilation semi-dynamique 1. Déclaration On réserve de la place sur la pile lors de l'allocation des variables locales. Compile[<nom> : Array [1..<n>] of Integer, <env>] et <env> local --> ?for i = 1 to <n> do ??(PUSH 0) 2. Accès en lecture Les accès s'effectuent comme précédemment. Seul change l'adresse de base qui se trouve sur la pile. Compile[<tab>[<expr>],<env>] --> ?Compile[<expr>, <env>]; ?(LOCAL A1 @at[<env>,<tab>])?; // recupere l'adresse de base ?(ADD A1 A1 A0); // ajoute l'offset ?(MOV A0 (A1)); // recherche indirecte de l'information. 3. Accès en écriture: Compile[<tab>[<expr1>]:= <expr2>,<env>] --> ?Compile[<expr1>, <env>]; ?(PUSH A0) ?Compile[<expr2>, <env>]; ?(LOCAL A1 @at[<env>,<tab>])?; // recupere l'adresse de base ?(POP A2);?// recupere la valeur de l'offset ?(MOV A1 A1 A2); // ajoute l'offset ?(MOV (A1) A0);?// sauvegarde indirecte Tableau et Compilation dynamiqueVar P: ^Array[1..6] of Integer; Compile[new(P), <env>] s = taille du type de P --> (ALLOCATE @s);?// general. un appel a une routine systeme (MOV (loc <P>) <A0>) // si P est une variable globale. Accès Les accès s'effectuent comme précédemment. Seul change l'adresse de base qui se trouve dans la variable P. La différence se situe dans l'appel indirect de la variable (opérateur ^ en Pascal et * en C). En lecture: Compile[<p>^[<expr>],<env>] --> ?Compile[<expr>, <env>]; ?(MOV A1 <P>) ?(MOV A1 (A1)); // recupere l'adresse de base (via l'indirect.) ?(ADD A1 A1 A0); // ajoute l'offset ?(MOV A0 (A1)); // recherche indirecte de l'information. En écriture: Compile[<tab>[<expr1>]:= <expr2>,<env>] --> ?Compile[<expr1>, <env>]; ?(PUSH A0) ?Compile[<expr2>, <env>]; ?(MOV A1 <P>) ?(MOV A1 (A1)); // recupere l'adresse de base (via l'indirect.) ?(POP A2);?// recupere la valeur de l'offset ?(MOV A1 A1 A2); // ajoute l'offset ?(MOV (A1) A0);?// sauvegarde indirecte Record (ou struct)On gère les record comme des tableaux. Seul change le fait que les valeurs sont de types différents et donc (normalement) de taille différente. R: Record a: Integer; b: Integer end; sera transformé en: R:?word 0?// A ?word 0?// B C'est le compilateur qui à la charge de faire le lien entre les noms de champs et l'indice de la valeur Compile[<rec>:Record <champ1>:<type1>;..;<champ1>:<type1> end, --> <nom> word 0; for i = 1 to <taille>-1 do word 0 On suppose que la table des symbole dispose des informations nécessaires ensuite pour transformer les noms des champs en offsets. Objets Même structure que pour les records. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
50
