Compilation et langages - TP 5 - Fonctions et conventions d'appel

L'objectif de cette séance est d'étendre le langage A6000 avec des fonctions définies par l'utilisateur.

Voici un exemple de programme complet, équivalent au programme Circle :

      main(integer x) (
        loop(0, x);
      )

      loop(integer i, integer r) (
        if line(point(i, r), r) then (
          loop(i+1, r);
        ) else ( );
      )
      
      integer point(integer i, integer r) (
        var integer j;
        j := 0;
        while (i*i + j*j < r*r) (
          j := j+1;
        );
        result := j;
      )

      boolean line(integer p, integer r) (
        var integer j;
        result := false;
        j := 0;
        while (j < r+1) (
          if j < p then (
            print(46);
            result := true;
          ) else (
            print(35);
          );
          print(32);
          j := j+1;
        );
        print(10);
      )

1. Description

1.1. Extension du langage source

1.1.1. Lexique

Le langage contient le nouveau symbole terminal , (virgule).

1.1.2. Grammaire

Les grammaires des instructions et des expressions sont étendues chacune d'une production pour l'appel d'une fonction (dans le cas d'une instruction, on parle aussi d'appel de procédure).

      [instruction] ← ...
                    |  [call]
             [expr] ← ...
                    |  [call]

             [call] ← {id} ( [arguments] )
        [arguments] ← ε
                    |  { [expression] , }* [expression]

On a également un nouveau non-terminal [fun_decl] pour la définition d'une fonction (qui généralise [main]), et un nouveau non-terminal [prog] pour un programme entier, constitué de plusieurs définitions de fonctions.

  [fun_decl] ← { [typ] }? {id} ( [parameters] ) ( [var_decls] [instructions] )

[parameters] ← ε
             |  { [typ] {id} , }* [typ] {id}

      [prog] ← { [fun_decl] }*

où { e }? signifie "e ou ε", et { e }* signifie "e répété 0 fois ou plus".

1.1.3. Sémantique

On choisit pour les paramètres des fonctions un mode de passage par valeur.

Lorsqu'une fonction a un type de retour ty, sa table des symboles contient une variable spéciale result de type ty et de sorte Return. Le résultat d'un appel de fonction est la dernière valeur qui a été affectée à la variable result. Le résultat d'une lecture de cette variable n'est pas spécifié.

Lorsqu'un appel de fonction est effectué dans une expressions, on attend que la fonction renvoie un résultat. Lorsque l'appel est une instruction, on attend que la fonction ne renvoie pas de résultat.

Un programme est un ensemble de fonctions, dans lequel on suppose qu'une des fonctions est nommée main. Invariablement, la fonction main attend un unique paramètre de type integer, et ne renvoie pas de résultat. Par défaut, les fonctions sont mutuellement récursives : chaque fonction d'un programme peut faire appel à n'importe quelle autre fonction du même programme. Exécuter le programme sur l'entrée n consiste à exécuter un appel de fonction main(n).

1.2. Extension du compilateur

1.2.1. Syntaxes abstraites

Dans la syntaxe abstraite source SourceAst, on définit un nouveau type désignant un appel de fonction

      call = string * expression list

constitué d'un identifiant (l'identifiant de la fonction appelée) et d'une liste d'expressions (les paramètres effectifs). Ce type est utilisé dans la définition de deux nouveaux constructeurs FunCall of call et ProcCall of call représentant respectivement un appel de fonction en position d'expression et d'instruction.

Les deux constructeurs FunCall et ProcCall sont traduits dans la représentation intermédiaire IrAst par les deux instructions

       FunCall of identifier * string * value list
      ProcCall of              string * value list

L'une et l'autre ont comme deux derniers arguments l'identifiant de la fonction appelée et la liste des paramètres formels. Le cas FunCall a en outre un premier argument indiquant le registre virtuel de destination du résultat renvoyé par la fonction.

Le type principal est maintenant program, qui est une table de symboles associant à chaque identifiant de fonction sa définition. La définition d'une fonction est donnée par le type

      type function_info = { 
        return:  typ option;
        formals: typ list;
        locals:  identifier_info Symb_Tbl.t;
        code:    block
      }

qui généralise le type main de la première séquence. Le champ return contient le type de l'éventuel résultat renvoyé par la fonction, et le champs formals la liste des types des paramètres de la fonction (pour cette séance il ne sera pas nécessaire de tenir compte de ces deux informations, qui n'interviendront que dans le TP8).
Remarquez que, dorénavant, chaque fonction possède sa propre table des symboles.

Dans la table des symboles utilisée pour les variables, le type identifier_kind est enrichi et offre maintenant trois sortes de variables :

Local désigne toujours les variables locales, introduites notamment avec var.
Formal(n) généralise et remplace FormalX et désigne le n-ème paramètre formel d'une fonction (FormalX correspond donc à Formal(1).
Return désigne la variable spéciale dans laquelle il faut écrire pour indiquer ce qu'est le résultat d'une fonction (uniquement dans le cas d'une fonction ayant un type de retour).

1.2.2. Conventions d'appel

La version de base décrite ici n'est pas immédiatement compatible avec l'allocation de registres, mais une extension facile permet de réparer ceci. Voir Sauvegarder les registres.

Dans les grandes lignes.
Les codes des différentes fonctions sont stockés l'un après l'autre en mémoire, chacun étiqueté par l'identifiant de la fonction correspondante, et en supposant que l'une des ces étiquettes est main. Lors de l'appel d'une fonction, l'appelant a la charge de réserver un emplacement sur la pile pour le résultat (si un résultat est attendu) et de placer les paramètres effectifs de l'appel sur la pile, puis de les retirer après le retour de la fonction. L'appelé a la charge de sauvegarder les registres $fp et $ra. Les variables locales sont toujours stockées dans la pile.

En détail.
Lors de l'exécution d'un appel de fonction f (a_0, ..., a_n), la pile a la forme suivante :

    |         |
    |---------|
    |         |    <- adresse pointée par l'ancien $fp (old_$fp)
    |         |
    |   ...   |    <- partie de la pile utilisée par le contexte appelant
    |         |
    |         |
    |---------|
    |   res   |    <- résultat de l'appel, le cas échéant
    |---------|
    |   a_1   |    
    |         |
    |   ...   |    <- arguments passés à f (paramètre effectifs)
    |         |
    |   a_n   |
  --|---------|-- Frontière entre ce qui est géré par l'appelant ou l'appelé
    | old_$fp |    
    |---------|
    |   $ra   |    <- pointeur $fp actuel
    |---------|
    |   x_0   |   
    |         |
    |   ...   |    <- variables locales de f
    |         |
    |   x_k   |    <- position du pointeur $sp au début du calcul de f
    |---------|
    |         |
    |   ...   |    <- partie de la pile utilisée pour les appels de fonction
    |         |	      réalisés par f

Le registre $fp contient une adresse dans la pile, qui sert de point de référence pour accéder aux variables locales. Il est mis à jour à chaque appel ou retour d'une fonction.

Une fonction accède à ses paramètres effectifs sur la pile en comptant un décalage positif par rapport au pointeur $fp, et à ses variables locales par un décalage négatif à partir de ce même point de référence. Par exemple, l'adresse du paramètre effectif a_n est obtenue en ajoutant 8 octets à l'adresse donnée par $fp, et l'adresse de la variable x_0 est obtenue en retirant 4 octets à l'adresse donnée par $fp. Commes pour les paramètres effectifs, l'emplacement de la variable spéciale result est accessible avec un décalage positif.
Tous ces éléments peuvent être traduits avec le constructeur Stack.

Lors de l'appel d'une fonction, l'appelant et l'appelé doivent procéder ainsi, dans l'ordre :

L'appelant réserve au sommet de la pile une place pour le résultat, si un résultat est attendu.
L'appelant place au sommet de la pile tous les arguments passés à la fonction, de gauche à droite.
L'appelant passe la main au code de la fonction appelée avec une instruction jal (jump-and-link, qui a pour effet de placer une adresse de retour dans le registre $ra).
L'appelé sauvegarde sur la pile les valeurs des registres $fp et $ra.
L'appelé définit la nouvelle valeur de $fp comme l'adresse à laquelle a été est stocké $ra sur la pile. Ceci doit aussi correspondre à ce stade à l'adresse indiquée par $sp.
L'appelé décale le pointeur $sp d'autant de cases que nécessaire pour laisser de la place à ses variables locales.
L'appelé exécute le code du corps de la fonction. À la fin de cette étape, l'éventuel résultat est censé être placé à l'emplacement de pile res alloué à la variable result.
L'appelé retire de la pile les valeurs sauvegardées de $fp et $ra et restaure ces registres avec ces valeurs.
L'appelé repasse la main à l'appelant en sautant à l'adresse de retour indiquée par $ra.
L'appelant retire de la pile les arguments qui avaient été donnés à la fonction (ce qui peut se faire par une simple modification de $sp).
Si l'appel devait produire une valeur, l'appelant transfère le résultat contenu dans res vers l'emplacement alloué pour cette valeur.

Ce processus entier ramène la pile dans l'état qui était le sien juste avant l'appel, et place l'éventuel résultat dans son emplacement de destination.

2. Travail attendu

Vous devez étendre chaque étape du compilateur pour intégrer les deux nouveaux aspects introduits dans ce sujet :

Définition d'une fonction
Appel d'une fonction

3. Extensions

3.1. Uniformisation

Maintenant que nous avons un mécanisme général pour l'appel de fonctions, il n'est plus nécessaire d'avoir la construction spéciale print.

Vous pouvez donc opérer un nettoyage consistant à :

retirer les constructeurs Print des syntaxes abstraites,
retirer les mots-clés correspondants des analyseurs,
produire dans l'assembleur final le code d'une fonction prédéfinie print (prédéfinie car l'utilisateur n'a pas besoin de la définir),
faire traiter les appels à print par le cas général des appels de fonction.

3.2. Variables globales

En l'état actuel, chaque fonction a ses variables locales, et l'exécution d'une fonction n'a aucun effet sur les variables locales d'une autre fonction. On peut en revanche ajouter au langage des variables globales, accessibles et modifiables par toutes les fonctions du programme.

Voici le modèle proposé pour intégrer des variables globales :

Dans la syntaxe concrète, on définit une variable globale par une ligne
```
	  var [type] [identifier] ;
```
placée avant les définitions de fonctions.
Dans la syntaxe abstraite, le type program contient une nouvelle table de symboles contenant ces variables globales, avec la nouvelle sorte Global (à ajouter au type identified_kind).
En mémoire, les variables globales sont allouées dans la zone des données statiques. Le programme code assembleur généré contient une zone .data, dans laquelle chaque variable globale définit une étiquette, et est initialisée à la valeur 0. En utilisant notre bibliothèque Mips, la déclaration d'une variable globale count se fait donc avec
```
	  label "count"
       @@ dword [0]
```
Pour accéder à une variable globale (en lecture ou en écriture), on utilise lw et sw, comme pour les données stockées dans la pile, en fournissant une adresse de base stockée dans un registre et un décalage. Pour placer dans un registre $r l'adresse de la variable d'étiquette count, on a l'instruction
```
	  la $r, "count"
```

3.3. Conventions d'appel, suite

Les conventions d'appel ne se limitent en général pas à la gestion de la pile, mais parlent aussi des registres.

3.3.1. Sauvegarder les registres (RECOMMANDÉ)

L'allocation des registres est faite fonction par fonction. Chaque fonction est donc susceptible d'utiliser les registres $ti pour stocker ses variables locales. Lorsqu'une fonction f appelle une fonction g (éventuellement f elle-même), les valeurs de ces registres doivent donc être sauvegardées pour ne pas être écrasées par l'exécution de g.

Étendre le protocole d'appel avec une étape 0 dans laquelle l'appelant enregistre au sommet de la pile les valeurs contenues dans les registres $t2 à $t9, et une étape 12 dans laquelle l'appelant restaure les valeurs de ces registres.

Une fois ce nouveau protocole en place, l'allocation de registres peut à nouveau être activée.

3.3.2. Paramètres et résultat

Les conventions usuelles de MIPS demandent que les valeurs des quatre premiers paramètres d'une fonction soient passées par les registres $a0 à $a3 plutôt que par la pile. De même, le résultat doit être transmis par le registre $v0.

Adapter le protocole d'appel pour intégrer cette nouvelle version.

De même que dans la section précédente il faut éviter que les valeurs contenues dans ces registres soient écrasées lors d'un appel à une autre fonction. Une stratégie pour cela consiste à créer de nouveaux registres virtuels pour les paramètres d'une fonction (au minimum pour les quatre premiers) et pour son résultat, et ajouter au protocole d'appel une étape 6' qui transfère vers ces registres virtuels les valeurs des paramètres et une étape 7' qui transfère le résultat de son registre virtuel vers $v0.

Pour des fonctions pas trop complexes, on peut s'attendre à ce que ces nouveaux registres virtuels soient affectés à des registres physiques, et dans tous les cas leur sauvegarde sera prise en charge par les mécanismes déjà en place.

Si vous avez implémenté l'optimisation de propagation des copies, elle peut également agir à ce niveau.

3.3.3. Affiner l'utilisation des registres

La version précédente sauvegarde systématiquement tous les registres temporaires à chaque appel de fonction. Cependant, tous ne contiennent pas des informations utiles.
Vous pouvez utiliser les informations de vivacité pour savoir quels registres contiennent des valeurs qui sont encore vivantes après un appel, et ne sauvegarder que celles-ci.

Les registres sont séparés en deux familles, selon que leurs valeurs doivent être sauvegardées par l'appelant (comme les $ti) ou par l'appelé (les $si).
Vous pouvez affiner l'algorithme d'allocation pour qu'il tente d'affecter aux registres $si les registres temporaires dont les valeurs sont vivantes à la fois avant et après une instruction FunCall ou ProcCall. Il faut également ajouter alors au protocole d'appel une étape 5' dans laquelle l'appelé sauvegarde sur la pile les valeurs de tous les registres $si qu'il est susceptible d'utiliser, et une étape 7'' dans laquelle ces valeurs sont restaurées.

Enfin, même les registres $ai ou $vi peuvent être utilisés lors de l'allocation de registres, lorsqu'ils ne sont pas utiles pour réaliser un appel de fonction.
Vous pouvez affiner l'algorithme d'allocation réaliser ceci. Une technique consiste à prévoir dans le graphe d'interférence des nœuds précolorés avec les $ai ou $vi.

3.4. Optimisation des appels terminaux

Un appel terminal n'a pas besoin d'allouer une nouvelle fenêtre d'activation sur la pile, et peut plutôt réutiliser celle de la fonction appelante.

Vous pouvez enfin intégrer à votre compilateur l'optimisation des appels terminaux. Pour éviter les problèmes liés aux fenêtres d'activation de tailles différentes, vous pouvez vous concentrer sur le cas des appels récursifs d'une même fonction.

Compilation et langages TP 5 - Fonctions et conventions d'appel