ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

COMPILATION ET LANGAGE

TP Arithmétique

Dans ce TP, on considère des expressions arithmétiques formées par :

• des constantes entières,
• les opérations +, -, * et /,
• des parenthèses ( et ) .

L'objectif est de produire du code MIPS évaluant de telles expressions et

affichant le résultat.

On rappelle qu'un programme MIPS s'écrit dans un fichier portant le suffixe

.asm ou .s et ayant la forme suivante :

.text
main:
...
li $v0, 10
syscall
.data
...

La partie qui suit l'annotation .text est le code du programme, et celle qui suit
l'annotation .data concerne des données statiques. L'étiquette main indique le
début du programme principal. L'appel à syscall déclenche une action en
fonction de la valeur stockée dans le registre $v0. En l'occurrence avec la
valeur 10, le programme s'arrête (il s'agit de l'appel exit).

Documentation.

Télécharger le simulateur MARS.

Avec ce simulateur, vous pouvez assembler un programme MIPS, puis

l'exécuter pas à pas et observer l'évolution des registres et de la mémoire.

1. Code MIPS à la main

ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

Écrire des programmes en assembleur pour évaluer et afficher les résultats

des expressions arithmétiques suivantes :

•4+6
• 21 * 2
•4+7/2
• 3 – 6 * (10 / 5)

Indications

• Pour placer une constante entière n dans un registre $r, vous pouvez
utiliser l'instruction li $r, n.
• Pour afficher un entier, il existe un appel système qu'on déclenche avec
l'instruction MIPS syscall quand la valeur stockée dans le registre $v0 est
1. Cet appel affiche sur la sortie standard l'entier contenu dans le registre
$a0.

2. Syntaxe abstraite et interprétation

Pour représenter les expressions arithmétiques, on utilisera le type Caml

expr défini de la manière suivante (dans [Link]) :

type binop = Plus | Minus | Mult | Div

type expr = Eint of int
| Ebinop of binop * expr * expr

L'expression Caml Eint n représente la valeur entière n, l'expression

Ebinop(op, e1, e2) représente l'application de l'opérateur op (par exemple :
Plus) aux deux expressions e1 et e2. Ainsi, l'expression 1 + (2 - 3) * 4 sera
représentée en Caml par :
Ebinop(Plus, Eint 1, Ebinop(Mult, Ebinop(Minus, Eint 2, Eint 3), Eint 4))

Aujourd'hui, vous n'avez pas besoin de construire vous-même ces valeurs

Caml, le squelette de programme que nous vous fournissons s'en charge
déjà.

Prise en main de la représentation Caml : un interprète

ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

Dans le fichier [Link], écrire une fonction récursive

interpret_expr : expr -> int

qui prend en entrée une expression arithmétique de type expr et renvoie

l'entier calculé par cette expression.

Éléments fournis

Pour cette première séance, nous vous fournissons un squelette constitué

de quelques fichiers Caml et d'un Makefile, ainsi qu'un jeu de tests. Vous
pouvez récupérer ces fichiers ici : [Link]. Une fois cette archive
décompressée avec tar xvf [Link], vous obtenez un répertoire TP1/
contenant les fichiers suivants :

Le code fourni compile ; pour le compiler, faire make dans un terminal, ou

mieux compiler depuis Emacs avec M-x compile ou encore C-c C-c. Ceci
crée un exécutable appelé compilo, qui lit un fichier dont le nom est passé
en argument et procède à sa compilation. Plus précisément, la commande

./compilo tests/[Link]

entrée dans un terminal lit le fichier [Link] présent dans le répertoire

tests, le compile, et affiche sur la sortie standard le code assembleur
généré. Pour enregistrer le résultat dans un fichier tests/[Link], vous
pouvez utiliser la ligne de commande.
./compilo tests/[Link] > tests/[Link]

Pour tester l'interprète, il faut utiliser la commande -i. Ainsi, la commande

ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

./compile -i tests/[Link]

interprète le programme contenu dans le fichier [Link] et affiche l'entier

obtenu. Bien sûr, pour l'instant le code fourni est incomplet, et toute tentative
d'exécuter l'interprète sur un programme Arith se soldera par une erreur
Failure("Not implemented") .
Lorsque la compilation échoue, vous pouvez vous placer automatiquement sur
l'erreur avec la commande M-x next-error ou encore Ctrl-x ` . Si ce raccourci
ne vous plaît pas, ajoutez une ligne à votre fichier .emacs, telle que (global-
set-key [f10] 'next-error) par exemple.

3. Génération de code MIPS

À partir d'une expression arithmétique de type expr, nous allons maintenant

générer automatiquement du code MIPS calculant cette expression et plaçant
le résultat dans le registre $a0. Nous commencerons avec une version simple
mais peu efficace, que nous améliorerons peu à peu.

3.1. Compilation à l'aide de la pile

Lors de la compilation d'une expression Ebinop(Plus, e1, e2) , il faut en

particulier produire un code assembleur code1 calculant le résultat de
l'expression e1 et le plaçant dans le registre $a0, ainsi qu'un code assembleur
code2 calculant le résultat de l'expression e2 et le plaçant également dans le
registre $a0. Pour éviter de perdre le résultat de e1, il faudra donc le
sauvegarder ailleurs avant d'exécuter le calcul de e2.
Dans cette première version, nous sauvegarderons le résultat de e1 au sommet
de la pile le temps du calcul du résultat de e2.

Question

Dans le fichier [Link], écrire une fonction récursive

compile_expr : expr -> unit

qui prend en entrée une expression arithmétique et affiche sur la sortie

standard un code MIPS qui calcule le résultat de l'expression en utilisant la
pile et place ce résultat dans le registre $a0.

Indications
ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

Le fichier [Link] contient déjà une fonction compile_toplevel_expr, qui

génère l'étiquette main: , le code affichant la valeur contenue dans le registre
$a0, et le code provoquand l'arrêt du programme. Cette fonction appelle votre
fonction compile_expr afin que le code qu'elle génère soit intégré au bon
endroit.

Pour l'affichage, le module Printf de Caml dispose d'une fonction printf que
l'on peut utiliser de manière similaire à la fonction printf du langage C.

Pour placer un élément au sommet de la pile, on peut utiliser les deux

instructions suivantes :

sub $sp, $sp, 4 # Déplace le sommet de la pile de 4 octets (= 1 mot)

sw $a0, 0($sp) # Enregistre le contenu de $a0 au sommet de la pile

Pour retirer un élément de la pile, on peut utiliser les deux instructions

suivantes :

lw $a1, 0($sp) # Place dans $a1 la valeur présente au sommet de la pile

add $sp, $sp, 4 # Déplace le sommet de la pile de 4 octets

Exemple : le code produit pour calculer l'expression 1 + (2 - 3) * 4 pourrait

être :

li $a0, 1 # Calcul de 1
sub $sp, $sp, 4 # Sauvegarde sur la pile
sw $a0, 0($sp)
li $a0, 2 # Calcul de 2
sub $sp, $sp, 4 # Sauvegarde sur la pile
sw $a0, 0($sp)
li $a0, 3 # Calcul de 3
lw $a1, 0($sp) # Chargement de 2 depuis la pile

add $sp, $sp, 4

sub $a0, $a1, $a0 # Calcul de 2 – 3
sub $sp, $sp, 4 # Sauvegarde sur la pile
sw $a0, 0($sp)
li $a0, 4 # Calcul de 4
ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

lw $a1, 0($sp) # Chargement de 2 - 3 sur la pile

add $sp, $sp, 4
mul $a0, $a1, $a0 # Calcul de (2 - 3) * 4
lw $a1, 0($sp) # Chargement de 1 depuis la pile
add $sp, $sp, 4
add $a0, $a1, $a0 # Calcul de 1 + (2 - 3) * 4

3.2. Compilation à l'aide de registres

Le code généré dans la version précédente est très mauvais : il n'utilise que les
deux registres $a0 et $a1, mais demande en contrepartie énormément de
manipulations de la pile qui auraient pu être évitées par l'utilisation de
registres supplémentaires. C'est d'autant plus fâcheux que les instructions
d'écriture et de lecture en mémoire sw et lw sont particulièrement coûteuses
sur un processeur réel.

Dans cette deuxième version, nous allons essayer de calculer le résultat

de l'expression passée en argument en utilisant uniquement les registres
$a0, $a1, $a2 et $a3, et pas du tout la pile. Le compilateur échouera si ces
quatre registres ne sont pas suffisants.

Question

Modifier la fonction compile_expr pour qu'elle prenne en argument

supplémentaire un entier i. Cette fonction doit générer un code MIPS plaçant
le résultat de l'expression arithmétique dans le registre $ai, sans modifier les
contenus des registres d'indice inférieur à i.

Indication

Le code produit pour calculer l'expression 1 + (2 - 3) * 4 pourrait être :

li $a0, 1 # Calcul de 1 dans $a0
li $a1, 2 # Calcul de 2 dans $a1
li $a2, 3 # Calcul de 3 dans $a2
sub $a1, $a1, $a2 # Calcul de 2 - 3 dans $a1
li $a2, 4 # Calcul de 4 dans $a2
mul $a1, $a1, $a2 # Calcul de (2 - 3) * 4 dans $a1
add $a0, $a0, $a1 # Calcul de 1 + (2 - 3) * 4 dans $a0
ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

Question bonus

Trouver une expression arithmétique faisant échouer ce compilateur par

manque de registres disponibles.

3.3. Bonne utilisation du jeu d'instructions

Dans le cas particulier où le second argument d'une opération

arithmétique est un entier pas trop grand, on peut donner directement
cet entier comme argument à l'opération arithmétique MIPS, sans passer
par un second registre. Ainsi, l'expression 2 - 3, qui est compilée ci-dessus
en

li $a1, 2 # Calcul de 2 dans $a1

li $a2, 3 # Calcul de 3 dans $a2
sub $a1, $a1, $a2 # Calcul de 2 - 3 dans $a1

pourrait être plus simplement traduite en

li $a1, 2 # Calcul de 2 dans $a1

sub $a1, $a1, 3 # Calcul de 2 - 3 dans $a1

Mieux, pour les opérations commutatives comme l'addition ou la

multiplication, l'ordre des opérandes peut être modifié : comme a + b est
égal à b + a, on peut compiler l'expression 1 + (2 - 3) * 4 de la même façon
que (2 - 3) * 4 + 1 et gagner une nouvelle opportunité d'appliquer
l'optimisation précédente. On peut ainsi aller jusqu'à n'utiliser que le
registre $a0 pour calculer le résultat de 1 + (2 - 3) * 4.

Question

Modifier la fonction compile_expr pour qu'elle produise du code optimisé

dans ces cas particuliers.

Question bonus

Trouver une expression arithmétique faisant échouer ce compilateur

malgré l'optimisation.
ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

3.4. Exploitation de l'ordre d'évaluation

Jusqu'ici, notre traitement d'une opération binaire e1 op e2 calcule

systématiquement le résultat de e1 d'abord, et stocke son résultat dans
un certain registre r1 pendant le calcul du résultat de e2.

Ainsi, si le calcul de l'expression e1 nécessite deux registres, et celui de

l'expression e2 nécessite quatre registres, nous aurons besoin au total de
cinq registres pour calculer l'expression complète : les quatre du calcul
e2, plus le registre qui est bloqué pendant ce temps pour le stockage du
résultat de e1.

En revanche, si l'ordre des calculs de e1 et e2 n'est pas important (ce qui

est le cas ici), on pourrait calculer d'abord e2 en utilisant quatre registres,
puis bloquer un unique registre pour stocker ce résultat et effectuer le
calcul de e1. Ainsi, pendant le calcul de e1, trois registres sont utilisés :
deux pour le calcul, et un pour le stockage du résultat de e2. Finalement,
nous n'aurions pas besoin dans ce cas de plus de quatre registres à la fois.

Question

Modifier la fonction compile_expr afin qu'elle calcule les valeurs des

opérandes dans l'ordre le plus favorable, c'est-à-dire en commençant par
l'opérande qui nécessite le moins de registres. Vous utiliserez pour ceci
une fonction auxiliaire

require : expr -> int

qui calcule le nombre de registres nécessaires pour le calcul de

l'expression donnée en argument, en supposant que les meilleurs choix
sont faits pour le calcul de cette expression.

Remarque
Cette technique est due à Sethi et Ullman, et il a été prouvé qu'elle était
optimale : elle organise le calcul du résultat d'une expression d'une
manière qui utilise le plus petit nombre possible de registres. Cependant...

Question bonus
ENI-ABT-BAMAKO Chargé du cours : Dr Yacouba GOITA

Trouver une expression arithmétique faisant encore échouer ce

compilateur malgré la gestion optimale des registres.

3.5. Gérer les dépassements de capacité avec la pile

Lorsque le nombre de registres est insuffisant, il est nécessaire d'avoir

recours à la pile pour stocker certains résultats intermédiaires.

Question

Modifier la fonction compile_expr pour qu'elle alloue les premières

valeurs intermédiaires dans les registres, et se rabatte sur la pile pour les
valeurs suivantes si nécessaire.

Question bonus

Trouver une expression arithmétique pour laquelle un débordement sur

la pile est nécessaire, mais pour lequel il serait plus malin de choisir
différemment les résultats intermédiaires à stocker dans des registres ou
sur la pile.