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.