Assembleur, solutions

L'énoncé est ici.

Fibonacci récursif

La solution est le fichier fib.spi.

Fibonacci itératif

La solution est le fichier fibiter.spi.

Compilation simple

La solution est le fichier enpile.ml Le code est plutôt simple, il généralise la fonction compile_expression du squelette. La mission de cette fonction est d'émettre le code correspondant à son argument, le résultat du calcul étant rangé dans v0.

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" 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 () ; binop op

Les fonctions push et pop empilent le registre résultat v0 et dépilent dans un registre temporaire (ici v1).

L'appel binop op émet le code qui réalise l'opération op, le premier argument étant dans v0 le second dans v1, le résultat est rangé dans v0 :

let memo_of_op = function | Plus -> "add" | Minus -> "sub" | Times -> "mul" | Div -> "div" let binop op = let memo =memo_of_op op in printf "\t%s $v0, $v0, $v1\t#%s\n" memo (String.uppercase memo)

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.

(* Le registre « $v0 » doit être le premier *) let memo_of_op = function | Plus -> "add" | Minus -> "sub" | Times -> "mul" | Div -> "div" 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 registre 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.

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 … » n'écrit que dans des registres dont les indices sont supérieurs ou égaux à i.

Bonne utilisation du jeu d'instructions

Voici un code 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'emettre le code asembleur, renvoie maintenant résultat de type arg qui dit où le code emis 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'utlisation 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 peu alors permuter les les deux sources afin de profiter des instructions à seconde 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 registre que nous verrons en cours.

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