Assembleur MIPS, solutions

Une solution est donnée dans le fichier fib.spi. Notons que la solution n’est pas unique, car on peut employer les registres et les emplacements de pile de différentes manières. Une autre solution est donnée dans fibvariant.spi. Elle est probablement plus efficace, car le cœur de la fonction fib utilise seulement quatre instructions lw et sw, contre six pour la solution précédente.

Fibonacci itératif

Compilation à l’aide de la pile

Voici une solution. On se donne deux fonctions auxiliaires push et pop. L’appel push r, où r est le nom d’un registre, (produit du code qui) empile le mot contenu dans r. L’appel pop r (produit du code qui) dépile un mot et le stocke dans le registre r.

let push r = printf "\t\ subu $sp, $sp, 4 sw %s, 0($sp) " r let pop r = printf "\t\ lw %s, 0($sp) addu $sp, $sp, 4 " r

La fonction compile_op traduit directement les quatre opérateurs arithmétiques en instructions MIPS.

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

Pour évaluer une expression de la forme e1 op e2, on évalue d’abord la sous-expression e1, et on sauvegarde son résultat, qui par convention est situé dans v0, sur la pile. Puis on évalue la sous-expression e2, 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 v1 et v0, en plaçant bien sûr le résultat dans v0.

let rec compile_expression = function | Int i -> printf " li $v0, %d\n" i | X -> printf " move $v0, $a0\n" | Binexp (op, e1, e2) -> compile_expression e1; push "$v0"; compile_expression e2; pop "$v1"; printf " %s $v0, $v1, $v0\n" (compile_op op)

Compilation à l’aide des registres

let registers : string array = [| "$a0"; "$v0" ; "$a1" ; "$a2" ; "$t0" ; |] let rec compile_expression r = function | Int i -> printf " li %s, %d\n" registers.(r) i | X -> printf " move %s, $a0\n" registers.(r) | Binexp (op, e1, e2) -> assert (r+1 < Array.length registers); compile_expression r e1; compile_expression (r+1) e2; printf " %s %s, %s, %s\n" (compile_op op) registers.(r) registers.(r) registers.(r+1) let compile_expression = compile_expression 1

Il n’est pas tout-à-fait immédiat que cette solution est correcte. Le code produit par le premier appel récursif à compile_expression place son résultat dans le registre d’indice r. Ce registre ne doit donc pas être affecté par le code qui évalue e2. De fait, c’est bien le cas, car le code produit par compile_expression r e2 ne modifie que des registres d’indice supérieur ou égal à r. Cette question a été étudiée dès 1967 par McCarthy et Painter, qui furent ainsi les pionniers de la preuve de correction de compilateurs.

Bonne utilisation du jeu d’instructions

let preserve result r = assert (result <= r); if result = r then r + 1 else r let rec compile_expression r = function | Int i -> printf " li %s, %d\n" registers.(r) i; r | X -> 0 | Binexp (op, e1, Int i) -> let r1 = compile_expression r e1 in printf " %s %s, %s, %d\n" (compile_op op) registers.(r) registers.(r1) i; r | Binexp (op, e1, e2) -> let r1 = compile_expression r e1 in let r2 = compile_expression (preserve r1 r) e2 in printf " %s %s, %s, %s\n" (compile_op op) registers.(r) registers.(r1) registers.(r2); r let compile_expression e = let r = compile_expression 1 e in if r <> 1 then printf " move $v0, %s\n" registers.(r)

La fonction compile_expression est modifiée pour renvoyer l’indice du registre où le résultat est stocké. Cet indice est en fait toujours r, sauf lorsque l’expression est la variable x, auquel cas on sait que la valeur est disponible dans le registre d’indice 0 (c’est-à-dire le registre a0) et on ne produit donc aucune instruction.

Les expressions binaires sont traitées en produisant d’abord le code correspondant à l’expression e1, qui produit un résultat dans le registre r1, puis le code correspondant à l’expression e2, qui produit un résultat dans le registre r2. Bien sûr, il faut éviter que ce second calcul écrase le contenu de r1, d’où l’appel à la fonction auxiliaire preserve r1 r, qui ajuste la valeur de r de façon à garantir r1 < r.

Les expressions binaires dont le second opérande est un entier sont reconnues et traitées spécialement. Ce traitement est trivial – de fait, ce sont des expressions unaires.

La version finale, non récursive, de compile_expression initialise r à la valeur 1, comme précédemment, et de plus, déplace si besoin le résultat du calcul du registre où il a été stocké (r) vers le registre où il est attendu (v0).

Bien sûr, ce code est un peu ad-hoc: il n’emploie pas les techniques modernes de genération de code et d’allocation de registres que nous verrons en cours.

Exploitation de la commutativité

Cette optimisation se fait en une ligne. Le motif qui décrivait les expressions binaires dont le second opérande est une constante entière est modifié pour filtrer également les expressions binaires dont l’opérateur est commutatif et dont le premier opérande est une constante entière.

let rec compile_expression r = function ... | Binexp ((Plus | Times) as op, Int i, e1) | Binexp (op, e1, Int i) -> let r1 = compile_expression r e1 in printf " %s %s, %s, %d\n" (compile_op op) registers.(r) registers.(r1) i; r ...

On notera que les motifs Binexp ((Plus | Times) as op, Int i, e1) et Binexp (op, e1, Int i) sont séparés par une disjonction: on accepte l’un ou l’autre. Cela est permis et a un sens car ces motifs lient les mêmes variables, à savoir op, e1 et i.

Exploitation de l’ordre d’évaluation

let rec usage = function | Int _ -> 1 | X -> 0 | Binexp ((Plus | Times), Int _, e1) | Binexp (_, e1, Int _) -> max (usage e1) 1 | Binexp (op, e1, e2) -> let u1 = usage e1 and u2 = usage e2 in min (max u1 ((if u1 = 0 then 0 else 1) + u2)) (max u2 ((if u2 = 0 then 0 else 1) + u1))

L’idée est de calculer le nombre de registres temporaires utilisés par compile_expression.

On sait que pour évaluer une constante entière, celle-ci utilise un registre, à savoir le registre r, dans lequel le résultat est placé.

Pour évaluer la variable x, on n’utilise aucun registre temporaire, car le résultat est disponible dans le registre a0.

Dans le cas particulier des expressions binaires dont un opérande est entier, on sait que l’on évalue d’abord e1, puis on effectue une opération dont le résultat est stocké dans r, donc on utilise successivement usage e1 registres puis 1 registre, soit au maximum max (usage e1) 1 registres.

Dans le cas des expressions binaires, supposons que l’on choisisse d’évaluer d’abord e1 puis e2. Alors, on utilisera d’abord u1 registres pour évaluer e1, puis on stockera le résultat de e1 pendant que l’on évalue e2. Stocker le résultat de e1 exige en général 1 registre, sauf dans le cas particulier où u1 = 0, car alors e1 est la variable x, l’appel preserve r1 r renvoie r, et on utilise en fait 0 registre. Stocker le résultat de e1 nécessite donc en général (if u1 = 0 then 0 else 1) registres. Stocker ce résultat tout en évaluant e2 exige donc (if u1 = 0 then 0 else 1) + u2 registres. Évaluer d’abord e1 puis e2 exige donc max u1 ((if u1 = 0 then 0 else 1) + u2) registres. Si l’on fait le choix opposé, à savoir évaluer d’abord e2 puis e1, il faudra donc, symétriquement, max u2 ((if u2 = 0 then 0 else 1) + u1) registres. Si l’on fait le meilleur choix, ce qui est notre intention, le nombre de registres nécessaires sera le minimum de ces deux valeurs.

La définition de la fonction usage, qui va guider l’optimisation, doit donc tenir compte de l’existence même de l’optimisation! Il y a là une apparente circularité qui est assez surprenante et élégante.

Une fois usage définie, il ne reste plus qu’à modifier compile_expression pour effectuer le meilleur choix. Seul le cas des expressions binaires est affecté:

let rec compile_expression r = function | Int i -> printf " li %s, %d\n" registers.(r) i; r | X -> 0 | Binexp ((Plus | Times) as op, Int i, e1) | Binexp (op, e1, Int i) -> let r1 = compile_expression r e1 in printf " %s %s, %s, %d\n" (compile_op op) registers.(r) registers.(r1) i; r | Binexp (op, e1, e2) -> let u1 = usage e1 and u2 = usage e2 in if (max u1 ((if u1 = 0 then 0 else 1) + u2)) < (max u2 ((if u2 = 0 then 0 else 1) + u1)) then let r1 = compile_expression r e1 in let r2 = compile_expression (preserve r1 r) e2 in printf " %s %s, %s, %s\n" (compile_op op) registers.(r) registers.(r1) registers.(r2); r else let r2 = compile_expression r e2 in let r1 = compile_expression (preserve r2 r) e1 in printf " %s %s, %s, %s\n" (compile_op op) registers.(r) registers.(r1) registers.(r2); r

Cette version du code est inefficace, car l’appel à usage depuis compile_expression induit une complexité quadratique. Pour cet exercice, ce n’est pas grave. Si l’on voulait faire mieux, on pourrait calculer une fois pour toutes la valeur de usage en chaque nœud de l’arbre, ce qui aurait un coût linéaire.

Cet algorithme de compilation a été étudié par Sethi et Ullman, qui en démontré la correction et l’optimalité. Voir également le livre d’Andrew Appel, Modern compiler implementation in ML, pages 250–253.