Assembleur MIPS, solutions

Fibonacci récursif

La solution est le fichier fib.spi.

Fibonacci itératif

La solution est le fichier fibiter.spi.

Compilation simple

Voici une solution. La fonction push (produit du code qui) empile le contenu du registre v0, tandis que pop (produit du code qui) dépile un mot et le stocke dans le registre v1.

let push () =
  printf "\tsub  $sp,$sp, 4\t\t#PUSH\n" ;
  printf "\tsw   $v0, 0($sp)\n"

and pop () =
  printf "\tlw   $v1, 0($sp)\n" ;
  printf "\tadd  $sp,$sp, 4\t\t#POP\n"

La fonction compile_expression (produit du code qui) évalue l’expression fournie et produit un résultat dans v0.

let rec compile_expression = function
  | Int i ->
      printf "\tli   $v0, %d\t\t#CONST %d\n" i i
  | X ->
      printf "\tmove $v0, $a0\t\t#VAR\n" 
  | Binexp (op, e1, e2) ->
      compile_expression e2 ;
      push () ;
      compile_expression e1 ;
      pop () ;
      let memo = match op with
      | Plus -> "add"
      | Minus -> "sub"
      | Times -> "mul"
      | Div   -> "div"
      in
      printf "\t%s  $v0, $v0, $v1\t#%s\n" memo (String.uppercase memo)

Pour effectuer une opération binaire, on évalue d’abord la seconde sous-expression (par exemple), et on sauvegarde son résultat, qui par convention est situé dans v0, sur la pile. Puis on évalue la première sous-expression, dont le résultat se trouve alors dans v0. On place alors dans v1 le résultat précédent, et il ne reste plus qu’à appliquer l’opérateur binaire souhaité aux registres v0 et v1, en plaçant bien sûr le résultat dans v0.

Du point de vue de la programmation, on notera l’utilisation de printf.

Compilation en registres

Il suffit de traduire la définition donnée de la fonction C en Caml.

let memo_of_op = function
  | Plus -> "add"
  | Minus -> "sub"
  | Times -> "mul"
  | Div   -> "div"

(* Le registre « $v0 » doit être le premier *)
let registers = [| "$v0" ; "$a1" ; "$a2" ; "$t0" ; |]

let rec do_compile target e = match e with
| Int i -> printf "\tli   %s, %d\n" registers.(target) i
| X     -> printf "\tmove %s, $a0\n"  registers.(target)
| Binexp (op, e1, e2) ->
    do_compile target e1 ;
    do_compile (target+1) e2 ;
    printf "\t%s   %s, %s, %s\n"
      (memo_of_op op)
      registers.(target) registers.(target) registers.(target+1)

let compile_expression e = do_compile 0 e

L’allocation des registres est faite à l’aide du paramètre target de la fonction do_compile. Cet entier target est l’indice (dans le tableau registers) du premier registre disponible, étant entendu que ceux d’indices inférieurs sont indisponibles.

Il n’est pas tout-à-fait immédiat que cette fonction est correcte. Considérons les appels récursifs :

    do_compile target e1 ;
    do_compile (target+1) e2 ;

Le résultat du calcul de e₁ est présent dans le registre d’indice target. Ce registre ne doit donc pas être modifié par le code qui calcule e₂. C’est bien le cas puisque, comme on le prouverait facilement, le code produit par un appel « do_compile i ... » ne modifie que des registres d’indice supérieur ou égal à i.

On remarquera également qu’aucun registre n’est perdu, au sens où tous les registres considérés comme indisponibles servent effectivement à garder un résultat utile pour la suite.

Bonne utilisation du jeu d’instructions

Voici une solution possible.

let registers = [| "$a0" ; "$v0" ; "$a1" ; "$a2" ; "$t0" ; |]

type arg = I of int | R of int

let parg chan = function
  | I i -> fprintf chan "%d" i
  | R r -> fprintf chan "%s" registers.(r)

let to_reg t a = match a with
| I i ->
    printf "\tli     %s, %d\n" registers.(t) i ;
    t, (t+1)
| R r ->
    r, t

let rec do_compile target e = match e with
| Int i -> I i, target
| X     -> R 0, target
| Binexp (Plus|Times as op, (Int _ as e1), e2) ->
     compile_bin target op e2 e1
| Binexp (op, e1, e2) -> compile_bin target op e1 e2

and compile_bin target op e1 e2 =
  let a1, t1 = do_compile target e1 in
  let r1, t1 = to_reg t1 a1 in
  let a2, _  = do_compile t1 e2 in
  fprintf stdout "\t%s   %s, %s, %a\n"
    (memo_of_op op) registers.(target) registers.(r1)
    parg a2 ;
  R target, target+1

let compile_expression e =
  let r,_ = do_compile 1 e in
  match r with
  | R 1 -> ()
  | R r ->
      printf "\tmove %s, %s\n" registers.(1) registers.(r)
  | I i ->
      printf "\tli     %s, %d\n" registers.(1) i

Par rapport aux solutions précédentes ça se complique un peu.

• La fonction do_compile, en plus d’émettre le code assembleur, renvoie maintenant un résultat de type arg qui dit où le code émis a rangé le résultat.
• L’allocation des registres reste simple, l’argument target de do_compile est l’indice du registre où ranger le résultat du calcul, mais do_compile n’utilise pas forcément ce registre. Il faut donc suivre les évolutions de ce paramètre. Dès lors la fonction do_compile renvoie en fait une paire dont la deuxième composante est l’indice du prochain registre libre.
• On notera l’utilisation de %a dans le format de fprintf, qui permet d’appeler un imprimeur arbitraire (ici parg pour afficher les valeurs de type arg).
• Le code fait un effort pour repérer les opérations commutatives dont la première source est un entier, on peut alors permuter les deux sources afin de profiter des instructions à première source entière. Notez le motif de filtrage utilisé.

Enfin le code ci-dessus est un peu ad-hoc: il n’emploie pas les techniques de genération de code et d’allocation de registres que nous verrons en cours.

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