Avertissement

On utilise abondamment le simulateur spim (manuel de spim). Il y a deux versions, l’une en ligne de commande (spim), l’autre avec des fenêtres (xspim). La seconde est plus abordable. On peut notamment utiliser assez facilement le mode pas-à-pas (step) et visualiser le code machine.

Fonction de Fibonacci

Comme fonction récursive

La définition de la fonction de Fibonacci est bien connue:

let rec fib n =
  if n <= 1 then
    1
  else
    fib (n-1) + fib (n-2)

Ecrire cette fonction en assembleur MIPS. Le programme assembleur fib.spi devra lire l’argument au clavier et afficher le résultat à l’écran. Il est lancé par la commande:

# xspim -notrap -file fib.spi

La démarche suggérée est d’écrire un programme en trois fonctions, read, writeln et fib. La fonction read lit un entier au clavier, elle consiste simplement à faire un appel système (voir les appels système dans le manuel de spim). La fonction writeln écrit un entier à l’écran puis retourne à la ligne, elle se déduit facilement de la fonction read et de la fonction hello_world donnée dans le cours. La fonction fib proprement dite se déduit de la fonction fact du cours. Enfin le code de lancement appelle ces trois fonctions, ce code est étiqueté conventionnellement __start:

        .globl __start
__start:
        jal  read
        move $a0, $v0
        jal  fib
        move $a0, $v0
        jal  writeln
        li   $v0, 10      # Exit
        syscall

Comme boucle

Modifier le programme précédent afin de calculer fib en utilisant une boucle:

let fib n =
  let prec = ref 1
  and cur = ref 1 in
  for i = 2 to n do
    let save = !cur in
    cur := !prec + !cur ;
    prec := save
  done ;
  !cur

Vous pouvez vous inspirer du codage de la boucle while du cours.

Le but de cet exercice est l’écriture d’un petit compilateur pour les expressions arithmétiques. Le compilateur sera de plus en plus malin.

Le compilateur zyva lit une expression sur son entrée standard et produit le code qui calcule cette expression sur sa sortie standard.

Environnement

Le programme zyva est un compilateur complet. Mais tout ou presque est déjà écrit, les parties données (analyseurs lexicaux et syntaxiques, code de lancement) le sont sous forme d’une archive. Pour démarrer, la démarche est la suivante:

1. Récupérer pgm.tar.
2. Expanser l’archive.

   # tar xvf pgm.tar
   

Le sous-répertoire pgm contient maintenant les sources, plus un Makefile adapté. On peut compiler le tout:

# cd pgm
# make
ocamllex lexer.mll
11 states, 267 transitions, table size 1134 bytes
ocamlyacc parser.mly
   ...
ocamlc -o zyva lexer.cmo parser.cmo arithmetique.cmo zyva.cmo

Cependant, le compilateur ainsi produit ne fonctionne pas:

# echo x+2 | ./zyva
...
eval:
Fatal error: exception Failure("Pas implémenté!")

C’est bien logique, il manque un bout de source important.

Ce qu’il faut faire

Il faut compléter le fichier arithmetique.ml. L’auteur de ce fichier a triché en écrivant failwith "Pas implémenté!" (ce qui provoque le lancement d’une exception) au lieu d’implémenter la génération de code pour les opérateurs arithmétiques.

Si l’on regarde l’interface arithmetique.mli la mission du compilateur est claire.

(*
   Ce module implante le compilateur proprement dit.

-- En entrée: une expression arithmétique avec une seule variable "x"
-- En sortie: un programme assembleur qui lit un entier représentant
              la valeur souhaitée pour "x" et calcule la valeur de
              l'expression. Le programme sera imprimé sur la sortie
              standard.
*)

val compile : Expression.expression -> unit

Avant de compléter le compilateur, commencez par examiner le code existant dans arithmetique.ml. Il s’occupe de la génération du code de lancement (fonctions prelude et postlude). C’est la fonction de compilation centrale (compile_expr) qui est incomplète: elle ne fonctionne que pour les variables et les constantes entières. En effet, le langage des expressions arithmétiques est donné par les déclarations de type du fichier expression.mli :

(* Les quatre opérateurs arithmétiques *)
type binop = Plus | Minus | Times | Div

type expression =
(* Opération binaire *)
  | Binexp of binop * expression * expression
(* Constante entière *)
  | Int of int
(* Variable *)
  | X

Vous pouvez d’ores et déjà fabriquer zyva et l’essayer à l’aide d’une expression ne comportant pas d’opérations binaires:

1. Compiler (ici l’expression arithmétique est « x »):

   # echo x | ./zyva > simple.spi
   

2. Essayer:

   # spim -notrap -file simple.spi
   SPIM Version 7.0 of July 7, 2004
   Copyright 1990-2004 by James R. Larus (larus@cs.wisc.edu).
   All Rights Reserved.
   See the file README for a full copyright notice.
   3
   3
   4
   4
   0
   

   Le code de lancement contient une boucle: lire une valeur entière au clavier, évaluer l’expression en liant la variable x à cette valeur, afficher le résultat. La boucle continue tant que la valeur lue est non nulle.

Durant la compilation, la valeur de x est stockée dans le registre a0. Le résultat du calcul doit être produit dans v0. Par exemple, pour l’expression « x », le code produit se termine par:

eval:
 move $v0, $a0
 jr   $ra

Compilation simple

Le plus simple est d’utiliser la pile pour stocker les résultats des calculs intermédiaires (voir les mouvements de pile pour la fonction fact dans le cours), en n’utilisant qu’un nombre limité de registres pour effectuer les opérations arithmétiques.

La compilation consiste alors en un simple parcours de l’arbre représentant l’expression à compiler. Par exemple, pour l’expression « (x-1)*3 + x*x », on peut obtenir le code machine suivant, si elle est parcourue dans l’ordre postfixe.

eval:
        move $v0, $a0           #VAR
        sub  $sp,$sp, 4         #PUSH
        sw   $v0, 0($sp)
        move $v0, $a0           #VAR
        lw   $v1, 0($sp)
        add  $sp,$sp, 4         #POP
        mul  $v0, $v0, $v1      #MUL
        sub  $sp,$sp, 4         #PUSH
        sw   $v0, 0($sp)
        li   $v0, 3             #CONST 3
        sub  $sp,$sp, 4         #PUSH
        sw   $v0, 0($sp)
        li   $v0, 1             #CONST 1
        sub  $sp,$sp, 4         #PUSH
        sw   $v0, 0($sp)
        move $v0, $a0           #VAR
        lw   $v1, 0($sp)
        add  $sp,$sp, 4         #POP
        sub  $v0, $v0, $v1      #SUB
        lw   $v1, 0($sp)
        add  $sp,$sp, 4         #POP
        mul  $v0, $v0, $v1      #MUL
        lw   $v1, 0($sp)
        add  $sp,$sp, 4         #POP
        add  $v0, $v0, $v1      #ADD
        jr   $ra

En commentaire figurent des instructions équivalentes exprimées dans un hypothétique langage bytecode.

Compilation en registres

Le code ci-dessus est très mauvais. Le premier reproche majeur que l’on peut lui faire est une très mauvaise exploitation des registres.

Donc, supposons que nous disposons d’infiniment de registres r₀, r₁, … En pratique, pour cet exercice, on se limitera à un nombre fini de registres, dont les noms sont donnés par le tableau suivant:

let registers = [| "$v0" ; "$a1" ; "$a2" ; "$t0" ; |] (* tableau de quatre chaînes *)

Le compilateur allouera des registres dans l’ordre, à l’aide de ce tableau, et échouera s’il tombe à court de registres.

On définit alors la fonction de compilation C, qui prend en argument un registre r et une expression e à compiler. La mission de C est de produire le code qui calcule e et range le résultat dans r. Il y a trois cas de définition de C.

1. Si l’expression e est un entier i.

           li    r, i
   

2. Si l’expression e est la variable x, rangée, rappelons-le, dans le registre $a0.

           move r, $a0 
   

3. Enfin si e est par exemple une addition e₁ + e₂.

           C(r, e_1)
           C(r', e_2)
           add r, r, r'
   

   Où r′ est un registre différent de r.

Ainsi, pour l’expression « (x-1)*3 + x*x », on devrait obtenir plus ou moins ceci :

        move $v0, $a0
        li   $a1, 1
        sub   $v0, $v0, $a1
        li   $a1, 3
        mul   $v0, $v0, $a1
        move $a1, $a0
        move $a2, $a0
        mul   $a1, $a1, $a2
        add   $v0, $v0, $a1

Bonne utilisation du jeu d’instruction

Le code ci-dessus est encore criticable. Il contient des instructions inutiles.

• Des transferts de registre à registre. Par exemple, pour calculer « x*x » dans $a1, on a :

          move $a1, $a0
          move $a2, $a0
          mul   $a1, $a1, $a2
  

  C’est quand même assez mauvais puisque le code suivant fait exactement le même travail.

          mul   $a1, $a0, $a0
  

• Par ailleurs on peut calculer « x-1 » sans se donner la peine de ranger la constante 1 dans un registre, puisque le jeu d’instructions du MIPS autorise un (petit) entier comme second argument des opérations. Ici, on pourrait gagner deux instructions en remplaçant

          move $v0, $a0
          li   $a1, 1
          sub   $v0, $v0, $a1
  

  par

          sub   $v0, $a0, 1
  

Modifier la solution afin de produire du bon code dans ces cas particuliers. À l’arrivée, pour l’expression « (x-1)*3 + x*x », on devrait obtenir:

        sub   $v0, $a0, 1
        mul   $v0, $v0, 3
        mul   $a1, $a0, $a0
        add   $v0, $v0, $a1

On pourra également chercher dans un deuxième temps à exploiter la commutativité de l’addition et de la multiplication, afin de profiter des secondes sources entières. Ainsi au lieu de compiler « 1+x » comme:

        li     $v0, 1
        add   $v0, $v0, $a0

On pourrait produire :

        add   $v0, $a0, 1

Un autre exemple intéressant sur ce thème de la commutativité est l’expression « 1 + 2 * (x + 3 * (x + 4 * ( x + 5 * x))) ».

Encore plus loin

Il reste quelques détails…

• Que faire s’il n’y a, en dernière analyse, pas assez de registres? Il faut sans doute utiliser la pile...
• Comment utiliser un nombre minimum de registres? Cette question a été bien étudiée. On pourra consulter par exemple le livre d’Andrew Appel, « Modern compiler implementation in ML », pages 250–253.

Ce document a été traduit de L^AT_EX par H^EV^EA