Exercices
L'objectif de cette étude (A FAIRE SOUS LINUX) est de comprendre comment les instructions très simples reconnues par un microprocesseur permettent d'exécuter des programmes écrits dans des langages comme Python, Java, C++ etc.
Nous étudierons plus particulièrement comment coder en langage d'assemblage l'alternative (if ... then ... else), la boucle while, et l'appel de fonction.
Compétences visées:
- Expliquer comment traduire un programme Python simple en instructions pour un microprocesseur.
- Traduire une alternative en langage d'assemblage.
- Traduire une boucle en langage d'assemblage.
- Expliquer la réalisation par un microprocesseur d'un appel de fonction avec passage d'arguments.
- Coder une fonction récursive en utilisant une pile.
Notre processeur dispose d'une instruction de comparaison cmp permettant de comparer deux valeurs, et d'instructions de branchement beq et blt permettant de choisir la prochaine instruction à exécuter respectivement quand les deux valeurs sont égales, et quand la première est strictement inférieure à la seconde. L'instruction b permet de sauter sans condition à une adresse.
La description du processeur est disponible sur cette page.
Vous pouvez télécharger le kit pour ce BE, qui contient ce processeur (pour Logisim) ainsi qu'un programme permettant de transformer en code machine un programme écrit en langage d'assemblage (assembler.py).
Prise en main
Voici un exemple illustrant l'effet de l'instruction de comparaison et des instructions de branchement :
Copiez ce programme et collez-le dans un fichier nommé ex1.arm, puis utilisez la commande ./assembler.py ex1.arm dans un terminal pour assembler ce programme. Vous devez obtenir deux fichiers :
- ex1.lst est le fichier listing, qui reprend le code en langage d'assemblage et affiche les adresses et le code machine des instructions ;
- ex1.mem est le fichier qui contient le code machine de votre programme, prêt à être chargé dans la mémoire du processeur.
Lancez Logisim et ouvrez le fichier miniARM.circ qui contient le processeur. Chargez le fichier ex1.mem dans la mémoire (clic droit sur le composant mémoire, puis Load image... dans le menu). Initialisez l'unité de contrôle (clic droit sur le composant "Control Unit") et remettez le compteur ordinal à 0, activez la simulation ainsi que la génération des ticks d'horloge (vous pouvez régler leur fréquence dans le sous-menu Tick Frequency), et lancez le programme en cliquant sur A dans l'unité de contrôle. Le programme doit boucler sur l'adresse 0009 (ligne 6) car 5 est supérieur à 2.
Modifiez les valeurs dans le fichier ex1.arm (n'oubliez de l'assembler de nouveau et de charger le code machine en mémoire) et observez le comportement du programme.
Codage de l'alternative
L'alternative est une structure de contrôle qui permet de choisir les instructions à exécuter selon qu'une condition est vraie ou fausse. Par exemple, pour calculer la valeur absolue de la différence de deux entiers a et b en Python, on peut écrire :
Si a est strictement inférieur à b, on calcule d = b - a, sinon, on calcule d = a - b.
En utilisant par exemple les registres r0, r1 et r2 pour les variables a, b et d, codez ce programme en langage d'assemblage, assemblez-le et testez-le pour différentes valeurs de a et b.
Codez de manière similaire l'alternative pour les conditions :
- {$ a \neq b $}
- {$ a = b $}
- {$ a \leq b$}
- {$ a > b $}
- {$ a \geq b $}
Pour tester vos programmes, vous pouvez par exemple mettre un registre à 0 si la condition est fausse et le mettre à 1 si la condition est vraie.
Codage de la boucle
La boucle est une structure de contrôle qui permet de répéter l'exécution d'instructions tant qu'une condition est vérifiée. Par exemple, le code suivant calcule le reste de la division euclidienne de a par b :
En utilisant les registres r0 et r1 pour les variables a et b, codez ce programme en langage d'assemblage, assemblez-le, et testez-le pour différentes valeurs de a et b.
Calcul du PGCD de deux entiers Calcul du PGCD
Nous allons maintenant combiner l'utilisation de l'alternative et de la boucle pour calculer le PGCD de deux entiers par soustractions successives. Le programme Python correspondant est :
Codez ce programme en langage d'assemblage et testez-le pour différentes valeurs de a et b.
Appel de fonction Appel de fonction
Appeler une fonction, ce n'est finalement que sauter à l'adresse de sa première instruction. Mais une fois le code de la fonction exécuté, comment savoir où se trouve l'instruction qui suit l'appel, et qu'il faut maintenant exécuter ?
Il existe plusieurs solutions, et nous allons commencer par la plus simple, qui consiste à sauvegarder l'adresse de l'instruction qui suit l'appel (l'adresse de retour) dans un registre. Avec notre machine de cours dans le style ARM, on utilise généralement le registre r7 pour cela. L'exemple suivant montre comment appeler une fonction func (qui ne fait ici que rendre son argument plus 1) :
La ligne 1 (l'étiquette @main indique simplement qu'il s'agit du début de notre programme), place la valeur 5 dans le registre r0 qui est utilisé comme argument de la fonction. La ligne 2 place l'adresse de l'instruction qui suit l'appel de func dans le registre r7, afin que la fonction func puisse sauter à cette adresse lorsqu'elle a fini de s'exécuter. La ligne 3 saute à l'adresse de la première instruction de la fonction func. La ligne 4 récupère le résultat de la fonction (qui se trouve dans r0) et le place dans le registre r1. Les lignes 11 et 12 donnent le code de la fonction func : la ligne 11 incrémente le registre r0 (c'est ce que fait cette fonction peu intéressante en soi), et la ligne 12 saute à l'adresse contenue dans le registre r7, retournant donc juste après l'instruction d'appel de la ligne 3.
En vous inspirant de ce code, transformez le programme de calcul du PGCD afin qu'il appelle une fonction pgcd. Cette fonction recevra deux entiers dans les registres r0 et r1, et rendra leur pgcd dans le registre r0.
Vous verrez en étude de laboratoire que le processeur complet dispose d'une instruction bl (pour Branch and Link) qui permet de sauter à une adresse en sauvegardant automatiquement l'adresse de l'instruction suivante dans le registre r7 (appelé Link Register, ou lr car il permet de faire le lien entre les différents appels de fonctions). Ici, nous utilisons la capacité de l'assembleur à calculer la valeur des étiquettes (comme @retour) pour émuler ce comportement.
Pile et récursion
Si la fonction appelée en appelle une autre, elle écrase la valeur du registre r7, donc la solution présentée précédemment ne fonctionne pas dans tous les cas. Pour une fonction récursive, qui s'appelle elle-même un nombre indéterminé de fois, on ne peut même pas espérer s'en sortir en utilisant différents registres pour sauvegarder l'adresse de retour.
La solution consiste à utiliser une structure de donnée en mémoire appelée pile, car elle fonctionne comme une pile d'assiettes : on récupère en premier la dernière chose qu'on a empilée.
Nous utiliserons le registre r6 pour y ranger l'adresse de l'élément qui se trouve au sommet de la pile. L'assembleur qui vous est fourni accepte le nom symbolique sp (Stack Pointer) à la place de ce registre, ainsi que les instructions push et pop qui respectivement placent une valeur sur la pile et récupèrent (en la supprimant) la valeur présente au sommet de la pile. L'équivalent de push r0 est ainsi :
L'équivalent de pop r0 est :
En utilisant les pseudo-instructions push et pop, écrire un programme qui échange les valeurs des registres r0 et r1 sans utiliser d'autre registre.
Vous pouvez placer le code suivant : @pile smw 0 à la fin de votre programme pour que l'étiquette pile puisse être utilisée comme adresse de départ pour votre pile.
En utilisant les pseudo-instructions push et pop, écrire un programme qui calcule la somme des {$n$} premiers entiers en utilisant une fonction récursive. L'équivalent en Python serait :
Pour aller plus loin : calcul de la factorielleFactorielle
On souhaite calculer la factorielle d'un entier {$n$} : {$\displaystyle n! = \prod_{k = 1}^{n} k$}.
Le principe est le même que pour le calcul de la somme des {$n$} premiers entiers, mais comme notre processeur n'a pas d'instruction pour calculer le produit de deux entiers, il faudra écrire une fonction qui effectue ce calcul.
Écrire une fonction prod qui rend dans r0 le produit de r0 et de r1.
Écrire une fonction récursive fact qui utilise prod pour rendre dans r0 la factorielle de r0. On rappelle que par convention, {$0! = 1$}.