Assembleur

La solution est ici.

Avertissement

On utilise abondament le simulateur spim (son manuel). Il y a deux version l'un en mode ligne de commande spim et 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.

Partie I
Programmation assembleur

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)
Écrire 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, write et fib. La fonction write est donnée dans le cours. La fonction read se déduit facilement de write (voir les appels système). La fonction fib se déduit de la fonction fact. Enfin le code de lancement appelle ces trois fonctions, ce code est étiquetté conventionnelle __start. Vous aurez peut-être besoin de consulter la liste abrégée des instructions voir le manuel SPIM.
Voir la solution si besoin est.

Comme boucle

Modifier le programme précédent afin de calculer fib en utilisant une boucle :
let fib n =
  let prec = ref 1
  and curr = 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.
Voir la solution si besoin est.

Partie II
Compilation des expression arithmétiques

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 (shift-click).
  2. Expanser l'archive. 
    # tar xf pgm.tar
Le sous-repertoire pgm contient maintenant les sources, plus un Makefile adapté. Mais il manque le compilateur proprement dit (fichier arithmétique.ml). Si vous essayer de fabriquer zyva il se passe : 
# cd pgm
# make zyva
ocamllex lexer.mll
11 states, 267 transitions, table size 1134 bytes
ocamlc expression.mli
   ...
ocamlc -o zyva lexer.cmo parser.cmo arithmetique.cmo zyva.cmo
Cannot find file arithmetique.cmo
make: *** [zyva] Erreur 2
C'est bien logique, il manque un bout de source important.

Ce qu'il faut faire

Il faut écrire le fichier arithmetique.ml. Si l'on regarde l'interface arithmetique.mli la mission du compilateur est claire.
(* Compilateur proprement: compile e

  - Imprime le code qui réalise e sur la sortie standard
*)

val compile : Expression.expression -> unit

Pour écrire le compilateur partez du squelette donné.
  1. Récupérer le fichier squelette.ml.
  2. Mettez le dans pgm en changeant son nom. 
    # mv squelette.ml pgm/arithmetique.ml
  3. Fabriquer zyva. 
    # cd pgm
# make zyva
La compilation de zyva fonctionne alors. Mais le squelette est très incomplet. Il s'occupe de la génération du code de lancement, et contient une fonction de compilation (compile_expr) qui ne fonctionne que pour les entiers et les variables. En effet, le langage des expression arithmétique est rendu par les déclaration de type du fichier expression.mli :
(* Les quatre opérations *)
type binop = Plus | Minus | Times | Div

type expression =
(* Opérations *)
  | Binexp of binop * expression * expression
(* Entier *)
  | Int of int
(* Variable *)
  | X

Vous pouvez donc fabriquer zyva et l'essayer à l'aide de ce source simple.exp simple : « x ».
  1. Compiler simple.exp : 
    # ./zyva < simple.exp > simple.spi
  2. Essayer : 
    # spim -notrap -file simple.spi
SPIM Version 6.3a of January 14, 2001
Copyright 1990-2000 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
    Bref, le code de lancement contient une boucle lire un entier x au clavier, calculer l'expression (ici c'est x), l'afficher. La boucle continue tant que la valeur lue est non nulle.
Durant la compilation, la valeur de x est dans le registre a0 le résultat du calcul est rendu dans v0. Vous pouvez regarder simple.spi si besoin est :
eval:
 move $v0, $a0
 j $ra

Compilation simple

Le plus simple est de commencer par considérer des opérations en pile, avec accumulateur. Ansi, la soustraction place dans l'accumulateur la différence entre l'accumulateur et une valeur dépilée, (voir la compilation vers le bytecode et les mouvements de pile dans le cours)

La compilation ressemble alors fortement à un bête parcours post-fixe de l'expression. Pour l'expression « (x-1)*3 + x*x », on devrait alors sensiblement obtenir ce style de code machine (en commentaire les instructions correspondantes pour un bytecode « évident ») :
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
        j $ra
Voir la solution si besoin est.

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 r0, r1, ... En pratique pour cet exercice, on se limite à un nombre fini de registres en posant par exemple
let registers = [| "$v0" ; "$a1" ; "$a2" ; "$t0" ; |] (* tableau de quatre chaînes *)
Et on se place dans le cas ou il y a suffisament de registres.

On définit alors la fonction de compilation C, qui prend en argument un registre r et une expression à compiler. La mission de C est de produire le code qui calcule e et range le résultat dans r. Il 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 e1 + e2.
            C(r, e1)
            C(r', e2)
            add r, r, r'
    Où r' est un registre différent de r.
Ainsi dans l'exemple « (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
Voir la solution si besoin est.

Bonne utilisation du jeu d'instruction

Le code ci-dessus est encore criticable. Il contient des instructions inutiles. Modifier la solution afin de produire du bon code dans ces cas particuliers. Au final, 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 seconde sources entières. Ainsi au lien de compiler « 1+x » comme :
        li     $v0, 1
        add   $v0, $v0, $a0
On pourrait produire :
        add   $v0, $a0, 1
Voici un autre exemple intéressant sur ce thème de la commutativité.
Voir la solution si besoin est.

Encore plus loin

Il reste quelques détails...
Pas de solution, c'est une sorte de recherche personnelle. Vous aurez intérêt à chercher à vous simplifier la vie en vous attaquant aux diverses question indépendamment les unes des autres.
Ce document a été traduit de LATEX par HEVEA.