Fonction de Fibonacci

Comme fonction récursive

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

On souhaite traduire cette fonction en assembleur MIPS. Le programme assembleur fib.spi devra lire l’argument (un entier) sur l’entrée standard, effectuer le calcul, puis afficher le résultat (un entier, suivi d’un retour à la ligne) sur la sortie standard.

La démarche suggérée est de structurer le programme en trois fonctions, read, writeln et fib. La fonction read lit un entier sur l’entrée standard via un appel système (consulter la liste des appels système dans le manuel de spim ou bien en ligne). La fonction writeln affiche un entier suivi d’un retour à la ligne (on pourra s’aider de la fonction hello_world donnée en 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 reçoit par convention l’étiquette __start:

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

Pour commencer, vous pouvez copier le code ci-dessus dans un nouveau fichier fib.spi, puis lancer l’éditeur mars et ouvrir ce fichier.

Complétez le code. Si vous voulez, commencer par écrire les fonctions read et writeln, avec une fonction fib identité (qui renvoie son argument). Assemblez (Run/Assemble) puis exécutez le code (Run/Go) pour voir s’il fonctionne. Ensuite, écrivez la véritable fonction fib, et testez à nouveau.

Si votre code est syntaxiquement correct, alors vous pouvez également l’exécuter depuis la ligne de commande, à l’aide de spim:

  spim -notrap -file fib.spi

ou encore à l’aide de mars:

  mars nc fib.spi

L’option nc supprime l’affichage de la ligne de copyright de mars.

Comme boucle

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

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. 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.gz.
2. Expanser l’archive.

   # tar xvfz pgm.tar.gz
   

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
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.

La mission du compilateur, décrite dans l’interface arithmetique.mli, est simple:

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 :

Vous pouvez d’ores et déjà utiliser zyva pour compiler 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.

Compilation à l’aide de la pile

Le plus simple est d’utiliser la pile pour stocker les résultats des calculs intermédiaires, 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:

eval:
        move $v0, $a0
        subu $sp, $sp, 4
        sw   $v0, 0($sp)
        li   $v0, 1
        lw   $v1, 0($sp)
        addu $sp, $sp, 4
        sub  $v0, $v1, $v0
        subu $sp, $sp, 4
        sw   $v0, 0($sp)
        li   $v0, 3
        lw   $v1, 0($sp)
        addu $sp, $sp, 4
        mul  $v0, $v1, $v0
        subu $sp, $sp, 4
        sw   $v0, 0($sp)
        move $v0, $a0
        subu $sp, $sp, 4
        sw   $v0, 0($sp)
        move $v0, $a0
        lw   $v1, 0($sp)
        addu $sp, $sp, 4
        mul  $v0, $v1, $v0
        lw   $v1, 0($sp)
        addu $sp, $sp, 4
        add  $v0, $v1, $v0
        jr $ra

On pourra utiliser la commande make test, qui automatise ce test.

Compilation à l’aide des 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’un nombre fini de registres, dont les noms sont donnés par le tableau suivant:

Ce tableau étant fixé, nous pouvons faire références aux registres à l’aide d’indices entiers, par exemple 0, 1, 2, 3, 4.

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

On demande donc de modifier la fonction compile_expression pour prendre un argument un indice de registre r et une expression e. La fonction devra alors produire du code qui évalue l’expression e, place le résultat de ce calcul dans le registre d’indice r, et fait en sorte de ne pas modifier les valeurs stockées dans les registres d’indice inférieur à r.

Nous avons fait en sorte que le registre d’indice 0 soit a0, qui par convention contient la valeur de la variable x; ce registre est donc réservé et n’est pas disponible. Nous avons fait en sorte que le registre d’indice 1 soit v0, à savoir le registre dans lequel le résultat final est attendu. Ainsi, la fonction compile_expression 1 produira du code qui place son résultat dans v0, comme compile_expression précédemment.

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

eval:
        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
        jr $ra

Bonne utilisation du jeu d’instructions

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
  

On demande donc de modifier la solution afin de produire du bon code dans ces cas particuliers. En ce qui concerne le premier point, on fera en sorte que compile_expression r e renvoie l’indice du registre dans lequel il a choisi de stocker le résultat – soit r, soit un autre registre. En ce qui concerne le second point, on reconnaîtra les opérations binaires dont le second opérande est une constante.

Pour l’expression « (x-1)*3 + x*x », on devrait obtenir:

eval:
        sub  $v0, $a0, 1
        mul  $v0, $v0, 3
        mul  $a1, $a0, $a0
        add  $v0, $v0, $a1
        jr $ra

Exploitation de la commutativité

On pourra ensuite chercher à exploiter la commutativité de l’addition et de la multiplication. Ainsi, au lieu de compiler « 1+x » comme:

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

On pourrait produire :

        add   $v0, $a0, 1

Cette même optimisation devrait permettre de compiler l’expression « 1 + 2 * (x + 3 * (x + 4 * ( x + 5 * x))) » en n’utilisant qu’un seul registre temporaire.

Exploitation de l’ordre d’évaluation

Notre traitement des expressions binaires évalue d’abord e1, puis stocke son résultat dans un registre r1 pendant le calcul de e2. Mais, si l’ordre d’évaluation des expressions n’est pas important – ce qui est bien le cas ici – alors on pourrait aussi évaluer d’abord e2, puis stocker son résultat dans un registre r2 pendant le calcul de e1.

On voit que ce choix affecte le nombre U(e) de registres temporaires utilisés pour l’évaluation de l’expression e. Dans le premier cas, ce nombre est le maximum de U(e₁) et de 1+U(e₂). Dans le second cas, ce nombre est le maximum de U(e₂) et de 1+U(e₁). Si U(e₁) et U(e₂) diffèrent, alors la valeur de U(e) dépend du choix effectué. Or, on a intérêt à minimiser cette valeur, afin d’éviter d’employer un trop grand nombre de registres, ce qui pourrait nous amener à échouer ou bien à utiliser la pile.

Cette optimisation doit permettre de compiler l’expression « 1 - (1 - (1 - (1 - (1 - (1 - x))))) », très déséquilibrée à droite, en n’utilisant que deux registres temporaires (l’un pour stocker la constante 1, l’autre pour stocker le résultat intermédiaire du calcul, effectué de droite à gauche).

On demande d’abord d’écrire une fonction usage qui, appliquée à une expression e, indique combien de registres temporaires sont nécessaires pour l’évaluation de e. On demande ensuite de modifier le traitement des expressions binaires dans compile_expression pour utiliser usage et choisir intelligemment dans quel ordre évaluer les deux sous-expressions. On prendra garde au fait que l’existence même de cette optimisation doit être reflétée dans la définition de la fonction usage.

Encore plus loin

Il reste quelques détails... Par exemple, on pourrait faire en sorte que le compilateur n’échoue pas si le nombre de registres est insuffisant, mais utilise la pile.

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