AMIL: Assembleur miniature

dernière mise à jour : 08-12-2014

Objectifs

• utiliser le langage d’assemblage miniature
• traduction des structures conditionnelles et itératives

AMIL (Assembleur Miniature pour l’Informatique de Licence) est un programme développé par Pierre Boudes simulant l’exécution de programmes écrits en langage d’assemblage. Il s’agit d’un simulateur en ligne écrit en javascript. L’original est sur le site amil de Pierre Boudes.

Nous utilisons une version modifiée amill1s1 .

Description de l’architecture et du langage d’assemblage

AMIL permet de simuler un processeur disposant de

• 8 registres généraux R0 à R7 (contenant les opérandes et les résultats des calculs)
• un registre compteur de programme CP (contenant l’adresse de la prochaine instruction à exécuter)
• un registre instruction RI (contenant l’instruction en cours d’exécution)
• une unité arithmétique (mais pas logique) effectuant des calculs entiers et flottants

Le processeur est relié au travers d’un bus d’adresse et de données à une mémoire centrale de taille (pratiquemment) illimitée. Les cellules de cette mémoire centrale peuvent contenir soit une instruction, soit une valeur entière ou flottante. Les adresses de ces cellules commencent en 0. Les valeurs maximales utilisables sont celles de javascript (64bits en flottant, soit 2^53 en entier).

Le simulateur affiche l’ensemble processeur et mémoire centrale. Pour le processeur, seul le contenu des différents registres est affiché (pas l’UAL). La mémoire centrale est affichée à raison d’une cellule par ligne. Au démarrage, le simulateur est en mode édition de la mémoire centrale. L’utilisateur peut modifier interactivement le contenu de la mémoire centrale en y inscrivant les données et les instructions de son programme. La simulation peut ensuite être démarrée avec le bouton “Charger”. Le programme peut être simulé instruction par instruction (bouton “pas-à-pas”) ou jusqu’à sa terminaison éventuelle (bouton “Exécuter”). Le bouton “Reset” réinitialise le processeur en reprenant la simulation au début du programme. Un double click dans la zone de la mémoire principale permet de revenir au mode d’édition de la mémoire centrale.

Les mnémoniques utilisées pour les instructions sont de simples mots en français (il n’y a pas de format binaire défini). Les instructions possèdent deux champs d’adresse, l’opérande destination étant toujours placée en derniere position. Les registres sont symbolisés par leur noms en minuscules, r0 par exemple. Les valeurs litérales pour les nombres entiers présents dans les instructions utilisent la base 10 (pas de valeur en binaire ou héxadécimal). L’ensemble des instructions est le suivant:

• instructions de transfert de données

Mnémonique	Détail	Action	Adressage (op1/op2)
valeur x ri	Initialise le registre i avec la valeur x.	ri ← x	immédiat/registre
lecture i rj	Charge, dans le registre j, le contenu de la mémoire d’adresse i.	rj ← mem(i)	absolu/registre
ecriture ri j	Écrit le contenu du registre i dans la mémoire d’adresse j.	mem(j) ← ri	registre/absolu
lecture *ri rj	Charge, dans le registre j, le contenu de la mémoire dont l’adresse est la valeur du registre i.	rj ← mem(ri)	indirect/registre
ecriture ri *rj	Écrit le contenu du registre i dans la mémoire dont l’adresse est la valeur du registre j.	mem(rj) ← ri	registre/indirect
ecriture ri rj	Écrit le contenu du registre i dans le registre j.	rj ← ri	registre/registre

• instructions de calcul arithmétique. Les calculs sont réalisés en flottant. La division entière et le reste se comportent comme en Python.

Mnémonique	Détail	Action	Adressage (op1/op2)
negation ri	Calcule la négation du contenu du registre i.	ri ← − ri	registre
add ri rj	Ajoute la valeur du registre i à celle du registre j.	rj ← ri + rj	registre/registre
soustr ri rj	Soustrait la valeur du registre i à celle du registre j.	rj ← rj − ri	registre/registre
mult ri rj	Multiplie la valeur du registre j par celle du registre i.	rj ← rj * ri	registre/registre
div ri rj	divise la valeur du registre j par celle du registre i.	rj ← rj / ri	registre/registre
divent ri rj	quotient de la division de la valeur du registre j par celle du registre i. (division entière)	rj ← rj // ri	registre/registre
mod ri rj	reste de la division de la valeur du registre j par celle du registre i. (division entière)	rj ← rj % ri	registre/registre
add x ri	Ajoute x à la valeur du registre i.	ri ← ri + x	immédiat/regsitre
soustr x ri	Soustrait la valeur x à celle du registre i.	ri ← ri − x	immédiat/registre
mult x ri	Multiplie la valeur du registre i par x.	ri ← ri * x	immédiat/registre
div x ri	divise la valeur du registre i par x.	ri ← ri / x	immédiat/registre
divent x ri	quotient de la division de la valeur du registre i par x. (division entière)	ri ← ri // x	immédiat/registre
mod x ri	reste de la division de la valeur du registre i par x. (division entière)	ri ← ri % x	immédiat/registre

• instructions de saut. Il n’y a pas d’instructions de comparaisons spécifiques, les comparaisons font partie intégrante des instructions de saut. Les comparaisons opèrent sur l’un quelconque des regsitres généraux. Les instructions de saut utilisent un adressage absolu: l’adresse de saut est l’adresse en mémoire centrale de l’instruction cible. De manière pratique, les valeurs des adresses de saut se déterminent lorsque le programme a été écrit dans son ensemble.

Mnémonique	Détail	Action	Adressage (op1/op2)
saut i	Met le compteur de programme à la valeur i.	CP ← i	absolu
sautpos ri j	Si la valeur contenue dans le registre i est positive ou nulle, met le compteur de programme à la valeur j.	si ri ≥ 0 CP ← j sinon CP ← CP+1	registre/absolu
sautnul ri j	Si la valeur contenue dans le registre i est nulle, met le compteur de programme à la valeur j.	si ri = 0 CP ← j sinon CP ← CP+1	registre/absolu
sautnonnul ri j	Si la valeur contenue dans le registre i est non nulle, met le compteur de programme à la valeur j.	si ri ≠ 0 CP ← j sinon CP ← CP+1	registre/absolu

• instructions diverses, instructions de gestion de la pile, et instructions d’appel et retour de fonctions. Le processeur dispose d’instructions pour assurer la gestion d’une pile. Il utilise le registre R7 comme sommet de pile: R7 contient l’adresse en mémoire centrale du sommet de pile. La pile croît vers les adresses basses. La pile est également utilisée pour les appels et retours de fonctions.

Mnémonique	Détail	Action	Adressage (op1/op2)
stop	Arrête l’exécution du programme.
noop	N’effectue aucune opération.
empiler ri	Place la valeur contenue dans le registre i en haut de la pile.	mem(r7) ← ri, r7 ← r7 − 1	registre/implicite
depiler ri	Place la valeur en haut de la pile dans le registre ri.	ri ← mem(r7), r7 ← r7 + 1	registre/implicite
appel i	Appel de fonction à l’adresse i.	mem(r7) ← (CP+1), CP ← i, r7 ← r7 - 1	absolu/implicite
retour	Retour de fonction à l’appelant.	CP ← mem(r7), r7 ← r7 + 1	implicite

Ecrire un programme avec AMIL

Evaluation d’expressions

Nous reprenons l’exemple de la conversion Celsius/Fahrenheit que vous avez déjà réalisée en Python. Pour rappel, \(°F = (°C \times 9 / 5) + 32\). Concernant les données de cet exercice, nous avons une variable flottante en entrée (les degrés Celsius), 3 constantes entières (9, 5 et 32), et un résultat flottant. Ne connaissant pas encore l’emplacement de ces données en mémoire centrale, nous notons celsius l’adresse de la cellule contenant les degrés celsius, const5, const9, const32 les adresses des 3 constantes, et fahrenheit l’adresse de la cellule contenant le résultat. Le programme, avant placement des données, est écrit conformément au format des instructions de AMIL:

• les opérandes des calculs doivent préalablement être chargées dans des registres, le résultat est également dans un registre.
• les instructions de calcul ont deux champs adresse, l’un des registres opérandes contient également le résultat.
• les registres contenant les résultats des calculs intermédiaires sont réutilisés directement, il est inutile de stocker ces résultats en mémoire centrale (tant que nous disposons de suffisamment de registres).
• le choix des registres utilisés dans les calculs est à l’appréciation du programmeur. Nous n’avons pas de contraintes à ce sujet dans ce cas, nous choisirons d’utiliser les registres en commencant par R0 jusque R7 au fur et à mesure des besoins. Dans tous les cas, on cherchera à minimiser le nombre de registres utilisés.

Connaissant le nombre d’instructions du programme, il est possible de transformer cette première version du programme en remplacant les adresses des variables et des constantes (celsius, const5, const9, const32 et fahrenheit) avec des adresses en mémoire centrale. Une première solution consiste à placer les données directement à la suite du programme que nous avons écrit. Le programme comporant 7 instructions, nous aurons celsius égale 8, const5 égale 9, const9 égale 10, const32 égale 11, et fahrenheit égale 12. Une seconde solution consiste à placer les données avant le programme. Sachant que le processeur exécute toujours l’instruction située à l’adresse 0 lorsqu’il démarre, cette instruction sera une instruction de saut inconditionnel vers l’adresse de début du programme. L’adresse de début de programme est déterminée par le nombre de données utilisées par le programme (soit 5 ici, plus 1 pour l’instruction située à l’adresse 0). L’instruction à l’adresse 0 sera donc saut 6, et nous aurons celsius égale 1, const5 égale 2, const9 égale 3, const32 égale 4, et fahrenheit égale 5.

Avant placement des données	Données placées à la fin	Données placées au début	Utilisation du mode immédiat
0 lecture celsius r0 1 lecture const9 r1 2 mult r1 r0 3 lecture const5 r1 4 div r1 r0 5 lecture const32 r1 6 add r1 r0 7 ecriture r0 fahrenheit	0 lecture 8 r0 1 lecture 9 r1 2 mult r1 r0 3 lecture 10 r1 4 div r1 r0 5 lecture 11 r1 6 add r1 r0 7 ecriture r0 12 8 24.38 9 9 10 5 11 32 12 ?	0 saut 6 1 24.38 2 9 3 5 4 32 5 ? 6 lecture 1 r0 7 lecture 2 r1 8 mult r1 r0 9 lecture 3 r1 10 div r1 r0 11 lecture 4 r1 12 add r1 r0 13 ecriture r0 5	0 saut 3 1 24.38 2 ? 3 lecture 1 r0 4 mult 9 r0 5 div 5 r0 6 add 32 r0 7 ecriture r0 2

Une amélioration notable peut être apportée en utilisant les modes d’adressage proposés par AMIL. Toutes les instructions de calcul sont présentes avec un mode d’adressage immédiat, c’est à dire que la valeur d’une opérande entière peut être directement placée dans l’instruction. Notre conversion utilise 3 calculs avec des constantes entières, nous utilisons donc le mode d’adressage immédiat dans ce cas. Le programme est ainsi beaucoup plus court, et en plus, le calcul complet n’utilise plus qu’un seul registre.

1. Question Ecrivez un programme AMIL qui convertit un angle fourni en degrés, minutes et secondes d’arc en un angle en radians. Pour rappel, 360 degrés égalent \(2 \times \Pi\) radians, 60 minutes d’arc égalent un degré, 60 secondes d’arc valent une minute, et \(\Pi\) sera pris égal à 3.1415926535. Le résultat de la conversion sera placé dans le regitre R0.

 0  saut 5
 1  181
 2  34
 3  27.2516
 4  3.1415926535
 5 lecture 1 r0
 6 lecture 2 r1
 7 div 60 r1
 8 add r1 r0
 9 lecture 3 r1
10 div 3600 r1
11 add r1 r0
12 lecture 4 r1
13 mult 2 r1
14 mult r1 r0
15 div 360 r0

Structure conditionnelle

Les structures conditionnelles des langages de haut niveau se traduisent en AMIL à l’aide des instructions de saut conditionnelles sautpos ri j, sautnul ri j ou sautnonnul ri j. Le principe est d’évaluer (une partie de) l’expression correspondant à la condition de la structure conditionnelle dans un registre ri et d’utiliser l’une de ces trois instructions suivant la condition rencontrée. La détermination des adresses de saut se fait après traduction des parties de programme correspondantes aux branches de la structure conditionnelle. Nous illustrons ce principe avec le calcul du maximum de 2 variables. Notez que \(not(a < b) \equiv a \geq b \equiv (a-b) \geq 0\), cela implique que la branche du else correspond bien à \(a - b \geq 0\) (la valeur de \(a - b\) est calculée dans R0 par les 3 premières instructions). Notez également qu’une petite optimisation a été faite en regroupant l’écriture du résultat contenu dans R0 à la fin des 2 branches de la structure conditionnelle (à l’adresse 11).

En Python	Avec AMIL
a = 10 b = 7 if (a < b): max = b else: max = a	0 saut 4 1 10 2 7 3 ? 4 lecture 1 r0 5 lecture 2 r1 6 soustr r1 r0 7 sautpos r0 10 8 lecture 2 r0 9 saut 11 10 lecture 1 r0 11 ecriture r0 3

1. Question Ecrivez un programme AMIL qui calcule de la même manière le maximum de 3 variables.

Itération conditionnelle

Les structures d’itération des langages de haut niveau se traduisent en AMIL à l’aide des instructions de saut conditionnelles sautpos ri j, sautnul ri j ou sautnonnul ri j et de l’instruction de saut inconditionnel saut i. Le principe est d’évaluer (une partie de) l’expression correspondant à la condition de l’itération conditionnelle dans un registre ri et d’utiliser l’une des trois instructions conditionnelles suivant la condition rencontrée. L’instruction utilisée effectuera un branchement à la fin du bloc correspondant à une itération dans le cas où l’itération se termine. De plus à la fin de ce bloc est placée une instruction de saut inconditionnel vers le début de l’évaluation de la condition. Nous illustrons ce principe au calcul de la puissance \(a^n\). Notez l’utilisation d’un cinquième registre R4 utilisé pour calculer i - n, car sans instructions de comparaisons en AMIL, les tests sont destructifs (nous ne voulons pas perdre la valeur de la variable i, c’est pourquoi, à l’adresse 10, nous copions le registre R2 dans ce registre R4 avant d’effectuer la soustraction utilisée dans le test).

En Python	Avec AMIL
a = 2 n = 4 i = 0 s = 1 while (i < n): s = s * a i = i + 1	0 saut 6 1 2 2 4 3 0 4 1 5 ? 6 lecture 1 r0 7 lecture 2 r1 8 lecture 3 r2 9 lecture 4 r3 10 ecriture r2 r4 11 soustr r1 r4 12 sautpos r4 16 13 mult r0 r3 14 add 1 r2 15 saut 10 16 ecriture r3 5

1. Question Ecrivez un programme AMIL qui calcule le nième terme de la suite de Fibonacci.

Parcours de tableaux (facultatif)

Les tableaux sont des structures de données regroupant un ensemble d’éléments de même type dans des cellules mémoire contigues. Ils sont comparables aux listes de Python. L’accès à de telles structures de données se réalisent en utilisant le mode d’adressage indirect, qui est présent dans AMIL par l’intermédiaire des instructions lecture *ri rj et ecriture ri *rj. Le registre d’indirection (celui précédé d’une étoile en AMIL) contient l’adresse du premier élément du tableau. L’accès à l’élément d’indice i du tableau est réalisé en ajoutant la valeur de l’indice au contenu du registre d’indirection (en supposant qu’un élément du tableau occupe une seule cellule mémoire). Nous illustrons ce principe avec un programme qui multiplie par 2 chaque élément d’un tableau d’entiers.

En Python	Avec AMIL
n = 3 l = [1, 2, 3] i = 0 while (i < n): l[i] = 2 * l[i] i = i + 1	0 saut 6 1 3 2 1 3 2 4 3 5 0 6 lecture 1 r0 7 valeur 2 r1 8 lecture 5 r2 9 ecriture r2 r3 10 soustr r0 r3 11 sautpos r3 19 12 ecriture r2 r4 13 add r1 r4 14 lecture *r4 r5 15 mult 2 r5 16 ecriture r5 *r4 17 add 1 r2 18 saut 9 19 stop

1. Question Ecrivez un programme AMIL qui calcule la somme des éléments d’un tableau.

Appels de fonction (facultatif)

Les appels de fonction dans les langages de haut niveau se traduisent traditionnellement dans les langages d’assemblage en utilisant le mécanisme suivant:

• réserver sur la pile un espace pour stocker la valeur de retour
• empiler les paramètres
• utiliser l’instruction appel i avec i ayant pour valeur l’adresse de la fonction appelée (i.e. l’adresse de la première instruction correspondant à la traduction en langage d’assemblage de la fonction appelée). Pour rappel, l’instruction appel empile l’adresse de retour, qui n’est autre que la valeur du compteur de programme (après incrémentation), puis elle copie la valeur i dans le compteur de programme
• la foncion aura accès à ses paramètres et à la valeur de retour par l’intermédiaire de la pile. Elle utilise également la pile pour stocker ses propres variables locales et pour sauvegarder l’ensemble des registres qu’elle modifie. L’utilisation d’un registre pointeur de cadre FP peut simplifier la traduction des fonctions en rendant constants les déplacements utilisés pour ces accès dans la pile.
• la dernière instruction d’une fonction est l’instruction retour qui dépile la valeur en sommet de pile dans le registre compteur de programme. La valeur dépilée doit être la valeur de retour empilée par l’instruction appel exécutée lors de l’appel à la fonction.

Ce mécanisme permet de gérer l’imbrication, la récursivité et la réentrance des fonctions écrites dans les langages de haut niveau. Nous l’illustrons avec la défintion de deux fonctions, addition(a,b) qui renvoie la somme de ces deux paramètres et utilise une variable locale pour son calcul, et doubler(x) qui renvoie le double deson paramètre x et utilise un appel à addition(x,x) pour son calcul. Le registre R7 est le pointeur de pile de AMIL, nous utilisons par ailleurs le registre R6 comme pointeur de cadre FP et le registre R5 pour calculer les déplacements dans la pile lors des accès aux paramètres, valeur de retour ou variables locales.

En Python	Avec AMIL	Commentaires
def addition(a, b): s = a + b return s def doubler(x): return(addition(x, x)) score=100 score=doubler(score)	0 saut 47 1 100 2 empiler r6 3 ecriture r7 r6 4 empiler r0 5 empiler r1 6 empiler r5 7 soustr 1 r7 8 ecriture r6 r5 9 add 4 r5 10 lecture *r5 r0 11 ecriture r6 r5 12 add 3 r5 13 lecture *r5 r1 14 add r1 r0 15 ecriture r7 r5 16 add 1 r5 17 ecriture r0 *r5 18 ecriture r6 r5 19 add 5 r5 20 ecriture r0 *r5 21 add 1 r7 22 depiler r5 23 depiler r1 24 depiler r0 25 depiler r6 26 retour 27 empiler r6 28 ecriture r7 r6 29 empiler r0 30 empiler r5 31 ecriture r6 r5 32 add 3 r5 33 lecture *r5 r0 34 soustr 1 r7 35 empiler r0 36 empiler r0 37 appel 2 38 add 2 r7 39 depiler r0 40 ecriture r6 r5 41 add 4 r5 42 ecriture r0 *r5 43 depiler r5 44 depiler r0 45 depiler r6 46 retour 47 valeur 95 r7 48 lecture 1 r0 49 soustr 1 r7 50 empiler r0 51 appel 27 52 add 1 r7 53 depiler r0 54 ecriture r0 1 55 stop	saut prog princ. variable globale score addition push FP; FP = SP sauvegarde registres variable locale s SP = SP - 1 r5=FP depl param a = 4 r0 = a r5=FP depl param b = 3 r1 = b r0 = a + b r5=SP depl var locale s = 1 s = r0 r5 = FP depl val retour = 5 return s (=r0) oubli var locale s restauration registre retour addition doubler push FP; FP = SP sauvegarde registres r5=FP depl param x = 3 r0 = x val retour addition param a addition param b addition appel addition oubli parametres addition val retour addition(x,x) dans r0 r5=FP depl val retour = 4 return r0 restauration registres retour doubler prog. princ. init pile; r0=score val retour doubler param x doubler appel doubler oubli parametre doubler val retour doubler(x) dans r0 ecriture dans score

Récursivité (facultatif)

Nous illustrons la traduction d’une fonction récursive avec la fonction factorielle(n). Cet exemple montre bien l’intérêt d’utiliser une pile pour les appels de fonctions.

En Python	Avec AMIL	Commentaires
def factorielle(n): if n == 0: return 1 else: return n * factorielle(n-1) n = 3 f = factorielle(n)	0 saut 30 1 3 2 ? 3 empiler r6 4 ecriture r7 r6 5 empiler r0 6 empiler r1 7 empiler r5 8 ecriture r6 r5 9 add 3 r5 10 lecture *r5 r0 11 sautnonnul r0 14 12 valeur 1 r0 13 saut 22 14 ecriture r0 r1 15 soustr 1 r1 16 soustr 1 r7 17 empiler r1 18 appel 3 19 add 1 r7 20 depiler r1 21 mult r1 r0 22 ecriture r6 r5 23 add 4 r5 24 ecriture r0 *r5 25 depiler r5 26 depiler r1 27 depiler r0 28 depiler r6 29 retour 30 valeur 95 r7 31 lecture 1 r0 32 soustr 1 r7 33 empiler r0 34 appel 3 35 add 1 r7 36 depiler r0 37 ecriture r0 2 38 stop	saut prog princ. variable globale n variable globale f factorielle sauvegarde registres r5 = FP + 3 r0 = parametre n n == 0 ? oui r0=1 non r1 = n-1 val retour parametre n-1 appel récursif oubli parametre r1 = fact(n-1) r0 = r0 * fact(n-1) r5 = FP + 4 val retour = r0 restauration regsitres retour factorielle prog. princ.