On entend par code machine le langage du processeur de l’ordinateur. Le modèle d’un processeur est toujours sensiblement le même, il correspond grosso-modo au modèle de Van Neuman, modèle fondateur de l’ordinateur concret.
Selon ce modèle, l’ordinateur est composé en première approximation d’un processeur d’un banc de registres et d’une mémoire, la mémoire est un grand tableau d’entiers, dit aussi mots mémoire. Les registres sont une petite quantité de mémoire rapidement accessible. Le processeur lit une instruction à partir de la mémoire, l’exécute, lit une autre instruction l’exécute etc.
Les instructions du processeur sont élémentaires, ce peuvent être des lectures ou des écritures en mémoire, des opérations arithmétiques simples entières ou flottantes, des sauts (qui font que l’instruction exécutée ensuite ne suit pas l’instruction de saut dans la mémoire). Elle sont simples parce que réalisées par des circuits électroniques. L’innovation de Van Neuman est que le programme réside dans la mémoire et que le processeur l’interprète en quelque sorte. Une machine connue précédente (l’ENIAC) n’était pas un ordinateur au sens moderne, mais plutôt une grosse calculatrice : il n’existait pas à proprement parler de programme, pour calculer un résultat spécifique, il fallait changer les câblages entre les diverses unités de calcul. Par contraste la machine de Van Neuman est un calculateur dont la tâche est d’interpréter des programmes, on parle aussi de machine universelle.
En particulier, et c’est cela qui nous intéresse dans notre cours les programmes sont des données résidant en mémoire, ils peuvent être lus ou produits par d’autre programmes. En ce sens, la machine de Van Neuman ouvre la porte de la compilation.
On comprendra donc que les processeurs se ressemblent tous du point de vue de l’utilisateur, puisqu’ils se conforment tous au modèle initial. Les différences entre processeurs proviennent surtout du jeu d’instructions. On distingue :
Il faut tout de même reconnaître que le fossé entre RISC et CISC n’est pas aussi grand que l’on le pensait dans les années 80. Ici tout est affaire de degré. Les premiers processeurs RISC ne possédaient pas de multiplications câblée (sous prétexte que la multiplication est rare en pratique !), ce n’est plus le cas. À l’inverse, le Pentium (héritier du 8086) a un jeu d’instructions très varié, mais ses diverses incarnations exécutent bien les instructions en parallèle, ce qui était présenté comme propre aux purs RISC à l’origine.
On ne saurait passer sous silence le bytecode : le compilateur ne produit pas de code pour un processeur réel, mais pour un processeur conventionnel, une machine virtuelle. Les instructions, sont bien représentées par une suite d’entiers, mais c’est un programme qui les lira et les interprétera. Ce dernier programme est bien évidemment écrit dans un langage d’assez bas niveau, typiquement en C. L’avantage de cette technique est la portabilité, pour obtenir un système fonctionnant sur une nouvelle architecture, il n’y a pas besoin de modifier le compilateur, il suffit a priori de porter le programme qui implémente la machine virtuelle. On peut aller jusqu’à considérer que la portabilité s’applique aussi aux programmes compilés : « Compile once, run everywhere » comme on dit pour Java. C’est un peu exagéré en pratique, car un environnement d’exécution ne se compose pas, dans le cas de Java, seulement d’un processeur, mais aussi de nombreuses fonctions de librairie chargées dynamiquement qui doivent alors se trouver à la fois sur le lieu de compilation et sur celui de l’exécution. On comprend cependant bien le principe, qui autorise les applets de Java.
Évidemment, l’exécution de bytecode est plus lente que l’exécution directe de code du processeur, dit aussi code natif, car il y a, entre autres, un surcoût dû à la mécanique d’interprétation des instructions.
Des exemples de cette technique sont le système de Java (compilateur javac, machine virtuelle java) et le système Objective Caml (compilateur ocamlc, machine virtuelle ocamlrun). Notons que certains compilateurs Java produisent du code natif, tandis que Caml propose un compilateur natif (ocamlopt). Notons également qu’il est possible, lors, disons de la première exécution d’une fonction, de transformer le bytecode en instructions de la machine hôte, on parle alors de compilation à la volée (Just In Time ou JIT). Cela revient un peu à déléguer une partie de la compilation au moment de l’exécution et ne se justifie vraiment qu’en cas de chargement de code à l’exécution entre machines hétérogènes.
Dans le cas du bytecode, le concepteur du langage a le choix de la machine cible. Il va donc l’adapter au langage. C’est par exemple le cas de la machine Java qui fournit des instructions d’appel de méthode et de la machine Caml qui fournit des instructions d’appel de fermeture et des opérations arithmétiques sur les 31 bits de poids fort des entiers.
Pourtant une machine virtuelle peut à priori fournir une plate-forme d’exécution indépendante à la fois du langage (c’est bien ce que fait une machine réelle après tout) et de la machine réelle. C’est un peu le sens du projet .NET de Microsoft, mais il y a loin de la coupe au lèvres, le modèle de la machine .NET étant spécifiquement objet, et bien plus complexe qu’une machine réelle. Des développement sont d’ailleurs en cours dans le sens de l’extension de la machine machine .NET pour s’adapter aux langages fonctionnels.
Une référence intéressante sur la conception d’une machine virtuelle (celle de Caml-Light) est le rapport ZINC.
Dans ce cours nous considérerons un processeur RISC particulier : le MIPS, parce qu’il est simple et exemplaire des processeurs modernes, mais aussi parce que nous disposons d’un simulateur de ce processeur.
Le simulateur SPIM est disponible en http://www.cs.wisc.edu/~larus/spim.html. Voici des liens sur le manuel en HTML et en Postscript
Tous les processeurs modernes comportent une unité mémoire (MMU) qui permet de manipuler des adresses virtuelles, ie. de faire un renommage, transparent pour l’utilisateur, entre les adresses virtuelles du programme et les adresses réelles en mémoire.
Cela permet à chaque programme de choisir ses adresses indépendamment des autres programmes (qui peuvent être exécutés en même temps sur la même machine avec les mêmes adresses virtuelles mais des adresses réelles différentes).
Du point de vue de l’utilisateur, la mémoire est un (grand) tableau dont les
indices sont les adresses.
Généralement, la plus petite unité adressable dans la mémoire est
l’octet (8 bits) ou byte. Mais la taille naturelle des entiers
manipulés par
le processeur, c’est à dire la taille des entiers contenus dans les
registres, mais aussi la taille des adresses, est plus
grande, typiquement 32 ou 64 bits (soit 4 ou 8 octets).
On notera donc que sur un processeur 32 bits, les adresses des mots
mémoires successifs sont croissantes de 4 en 4.
Les accès à la mémoire non-alignés, c’est à dire
ceux qui ne correspondent pas à des adresses multiples de la taille
en octets de la valeur accédée, sont soit
interdits soit pénalisés.
Par exemple, pour le MIPS, l’instruction générique de lecture
d’un mot en mémoire lw exige des adresses multiples de 4.
La mémoire (virtuelle) d’un programme est partagée en zones. Il s’agit là, plus que d’une convention, d’un principe du système d’exploitation (ici Unix), organisateur de l’exécution des programmes.
Des adresses hautes vers les adresses basses :
| ||||||||||||||||||||||||||||||||||||
On distingue donc (du haut vers le bas) :
Le simulateur SPIM, va émuler cette vision de la mémoire (dans une zone par lui allouée). Dans une machine sans mémoire virtuelle on a généralement une organisation similaire, mais sans la protection contre l’écriture et la lecture dans les zones interdites.
Le MIPS comporte 32 registres généraux interchangeables, sauf
Les autres registres portent les numéros restants de 1 à 30. Comme cela n’est ni beau ni pratique, on leur donne des noms conventionnels. Ces noms correspondent à des utilisations préférentielles, qui seront détaillées par la suite.
|
Enfin et c’est assez important, il existe des registres spécifiques au processeur. Le principal est le compteur ordinal (program counter), noté pc. Le processeur incrémente le registre pc après la lecture d’une instruction et les instructions de saut écrivent dedans.
Le processeur Pentium ne possède que que huit registres d’usage général, dont les noms conventionnels sont du genre eax, ebx, ecx…
On peut voir les registres comme un tout petit peu de mémoire, très rapidement accessible. La bonne exploitation des registres compte pour beaucoup dans la rapidité d’un programme, car l’accès à une case de mémoire est bien plus coûteuse que l’accès à un registre. L’évolution en cours des processeurs et des mémoires ne fait que renforcer ce décalage, et la multiplications de caches toujours plus grands ne le résout que partiellement.
Il convient d’abord d’examiner les mode d’adressage c’est à dire l’expression des arguments des instructions. On utilise parfois le vocabulaire suivant :
| Immédiat | un entier |
| Direct | le contenu du registre |
| Indirect | le contenu de l’adresse contenu dans un registre |
| Indirect indexé | le contenu de l’adresse contenue dans le registre augmenté d’un déplacement |
Mais dans la description d’un processeur, il vaut mieux définir des symboles précis.
|
|
La plupart des instructions suivent le modèle
add r1, r2, o qui place dans r1 la valeur
r2 + o.
Les instructions qui interagissent avec la mémoire sont uniquement les instructions load et store.
lw r1, n(r2) place dans r1 le mot contenu à
l’adresse r2 + n.
sw r1, n (r2) place r1 dans le mot contenu à
l’adresse r2 + n.
Les instructions de contrôle conditionnel ou inconditionnel:
bne r, a, l saute à l’adresse l si r et a
sont différents,
jal o qui sauve pc+1 dans ra et saute à l’étiquette o.
Voici la liste des principales instructions :
|
|
L’aspect RISC est donc très notable.
On peut remarquer par exemple le fonctionnement de l’instruction
d’appel de fonction jal (jump and link).
L’adresse de retour de la fonction,
c’est à dire l’adresse de l’instruction qui suit le jal, est
rangée dans le registre ra.
Un CISC l’empilerait plutôt.
A contrario, les instructions synthétiques sont absentes, même les plus simples. Par exemple le Pentium possède une instruction d’empilage d’un registre, pushl r. Du point de vue RISC cette instruction diminue le pointeur de pile de la taille d’un mot et range le registre r à l’adresse pointée par le pointeur de pile. Soit en MIPS :
| sub $sp, $sp, 4 sw r,0($sp) |
Réaliser ces deux opérations en une seule instruction demande certainement de consacrer des transistors du processeurs et des bits de la définition du format des instruction à ce cas particulier. En conséquence de quoi, la logique de décodage des instructions va se compliquer. Un gain est cependant possible si le compilateur sait exploiter les instructions synthétiques à bon escient et si le processeur exécute les instructions fréquemment utilisées plus rapidement que leur décomposition en instructions plus simples.
Ils permettent l’interaction avec le système d’exploitation, et en dépendent. Le numéro de l’appel système est lu dans v0 (attention, ce n’est pas la convention standard). Selon l’appel, un argument supplémentaire peut être passé dans a0.
Le simulateur SPIM implémente les appels suivants:
|
Le langage assembleur (ou d’assemblage, beurk) est un langage symbolique qui donne des noms aux instructions (plus lisibles que des suites de bits). Il permet aussi l’utilisation d’étiquettes symboliques et de pseudo-instructions et de modes d’adressage surchargés.
Le langage machine est une suite d’instructions codées sur des mots (de 32 bits pour le MIPS). L’assembleur transforme ces instructions en instructions de la machine. Les étiquettes sont donc résolues (quand c’est possible !) et les pseudo-instructions remplacées par une ou plusieurs instructions machine.
L’assemblage est la traduction du langage d’assembleur en langage machine. Le résultat est un fichier objet qui contient, en plus du code, des informations de relocation qui permettent de lier (linker) le code de plusieurs programmes ensemble. Le programme final est donc un fichier dont la structure est à l’image de la description donnée pour la mémoire précédemment. Il restera à charger ce programme en mémoire et à le lancer, c’est le système d’exploitation qui s’en charge, lorsque l’utilisateur demande l’exécution du programme. L’adresse de lancement est contenue dans l’exécutable, ou a une valeur conventionnelle.
Dans le cadre de notre cours, le simulateur SPIM prend en entrée un fichier d’assembleur et réalise lui même l’assemblage, puis toutes les opération décrites jusqu’au lancement. L’édition de liens n’est pas réellement nécessaire, puisque qu’il n’y a ni fichiers multiples, ni librairies.
La traduction du langage machine en langage assembleur est facile. Elle permet de présenter les instructions machine (mots de 32 bits) sous une forme plus lisible. Le simulateur SPIM présente les instructions machines sous cette forme.
On se rend
alors compte dans le cas du MIPS que l’on ne retrouve pas toujours les
instructions du fichier initial. En effet, le langage compris par
l’assembleur est un peu étendu par rapport à celui du
processeur. Certaines des instructions propres à l’assembleur sont de
simples commodités :
move instruction de transfert d’un registre dans un autre est en
fait une addition de zéro.
D’autres pseudo-instructions se traduisent en quelques instructions,
c’est le cas de l’instruction li de chargement d’un entier
(32 bits) dans un registre, qui se traduit en un chargement des
16 bits de poids fort suivi d’un ou logique avec les 16 bits de
poids faible. Il est d’ailleurs logique qu’une machine dont les
instructions tiennent toutes sur 32 bits ne possède pas d’instruction
de chargement d’un entier de taille 32 bits.
Un cas important est celui des instructions de comparaison entre
registres et saut conditionnel.
Le processeur fournit en fait seulement deux instructions,
beq r1, r2, l et
bne r1, r2, l, à savoir effectuer le saut vers l si
les contenus des deux registres r1 et r2 sont respectivement
égaux ou différents.
On peut obtenir toutes les instructions de comparaison et saut :
blt (inférieur strict), bge (supérieur ou égal) etc.
en combinant les opérations de comparaison,
slt, sge, etc. et le test d’égalité au registre zero.
|
Pour voir, essayez :
où hello.spi est un fichier assembleur quelconque, et
regardez dans la zone dite Text Segment.
La zone Text Segment se présente sous la forme tabulée:
Adresse Instruction En clair Adresse Instruction machine machine symbolique assembleur
[0x00400000] 0x0109082a slt $1, $8, $9 ; 2: blt $t0, $t1, trois [0x00400004] 0x14200003 bne $1, $0, 12 [trois-0x00400004] [0x00400008] 0x3c01003d lui $1, 61 ; 4: li $t0, 4000020 [0x0040000c] 0x34280914 ori $8, $1, 2324 [0x00400010] 0x21280001 addi $8, $9, 1 ; 6: add $t0, $t1, 1 [0x00400014] 0x00094021 addu $8, $0, $9 ; 8: move $t0, $t1
On peut donc voir qu’à l’instruction assembleur blt $t0, $t1, trois
correspond deux instructions machine,
slt $1, $8, $9 et bne $1, $0, 12 [trois-0x00400004].
Cette section contient divers exemples de programmation en assembleur. Commençons par un premier exemple complet.
| .data hello: .asciiz "hello\n" # hello pointe vers "hello\n\0" .text .globl __start __start: li $v0, 4 # la primitive print_string la $a0, hello # a0 l'adresse de hello syscall |
On remarque les détails suivants.
.data et .text indiquent à
l’assembleur où ranger ce qui va suivre, respectivement dans
le segment statique de données et le segment de code.
$, pour les distinguer des autres symboles (ainsi on peut appeler une
étiquette v0).
.asciiz permet de décrire une chaîne de façon
usuelle (ici le caractère '\000' est ajouté à la fin
de la chaîne, selon la convention du langage C).
Le programme est assemblé, lié, chargé et lancé (ouf !) par :
| spim -notrap -file hello.spi |
Par convention le programme commence à l’étiquette __start.
Si on retire l’option -notrap, l’éditeur de liens ajoute un prélude
qui se branche à l’étiquette main (remplacer alors
__start par main).
On utilise des sauts conditionnels et inconditionnels:
Pascal la fonction minimum
| if t1 < t2 then t3 := t1 else t3 := t2 |
Assembleur Mips
| blt $t1, $t2, Then # si t1 < t2 saut à Then move $t3, $t2 # t3 := t2 j End # saut à End Then: move $t3, $t1 # t3 := t1 End: # suite du programme |
Pascal: calcule dans t2 = 0 la somme des entiers de 1 à t1
| while t1 > 0 do begin t2 := t2 + t1; t1 := t1 -1 end |
Programme équivalent
| Code Mips
|
On notera l’utilisation du registre $0 qui contient toujours zéro.
Une transcription alternative de la même boucle en assembleur est :
| j Test Loop: add $t2, $t2, $t1 sub $t1, $t1, 1 Test: bgt $t1, $0, Loop |
L’avantage est qu’une itération de boucle ne donne lieu qu’à un unique saut, contre deux sauts pour le code précédent. Il est probable que le second programme est plus rapide, mais cela demande à être vérifié, comme tout ce que l’on peut supposer sur la rapidité des programmes en assembleur.
Le processeur connaît les seules opérations élémentaires. Dès lors, lorsque l’on veut calculer une expression arithmétique, on décompose le calcul en étapes, en gardant les résultats intermédiaires dans des registres.
Pascal La distance
| v0 := a0 * a0 + a1 * a1 ; |
Assembleur Mips
| mul $t0, $a0, $a0 # un premier carré mul $t1, $a1, $a1 # le second add $v0, $t0, $t1 # la somme |
Les données statiques sont celles qui sont allouées par le compilateur. Dans un langage comme Pascal cela comprend au moins les variables globales.
| const N = 1000 ; var tableau : array [1..N] of integer ; c : char ; i : integer ; |
Ici on déclare un tableau de 1000 entiers, un caractère et un entier. En Pascal, la déclaration d’une variable entraîne l’allocation de l’espace mémoire nécessaire et l’établissement d’un lien entre le nom de la variable et l’adresse de l’espace mémoire réservé.
Un code assembleur équivalent sera :
| .data .align 2 # aligner sur un mot (2^2 octets) globaux: # début de la zone des globaux tableau: # adresse symbolique de tableau .space 4000 # taille en octets c: .space 1 # 1 octet .align 2 i: .space 4 # 4 octets |
On remarque les contraintes d’alignement introduites pour que les mots se trouvent bien à des adresses de mots. La directive .space n de l’assembleur alloue n octets dans le segment de données. Accessoirement la valeur initiale de ces octets est zéro.
On utilisera ensuite les noms symboliques pour accéder aux variables.
Par exemple, à une affectation
i := 10,
correspond le code assembleur suivant :
| .text la $a0, i li $v0, 10 sw $v0, 0($a0) |
Cette utilisation des noms symboliques est pratique, mais la
pseudo-instruction la s’expanse en deux instructions et on peut
faire mieux.
Supposons que l’adresse du début de la zone des globaux se trouve dans
un registre, par exemple le registre gp.
On pourra alors écrire plus directement :
| .text li $v0, 10 sw $v0, 4004($gp) |
Le chargement de l’adresse globaux dans gp ne pose pas
de problème, on l’effectuera dans un code de mise en route à l’aide de
l’instruction la déjà vue.
Mais il faut connaître le décalage entre le début de la zone des
globaux et l’adresse de i et il faut aussi que le déplacement
tienne sur 16 bits. Or, un compilateur connaît la taille des données,
et peut au moins contrôler la taille des décalages, voir implémenter
une politique plus raffinée (un pointeur de données globales par groupe
de fonctions, par exemple).
Notons que l’assembleur peut aussi nous aider un peu, car on peut définir une
constante symbolique égale à ce décalage.
| ioff = 4004 .text li $v0, 10 sw $v0, ioff($gp) |
Certains assembleurs et éditeurs de liens pourraient même accepter une
définition du style ioff = i-globaux, ce n’est pas le cas de
SPIM.
Dans certains langages comme C on peut à la fois définir et initialiser une variable globale :
| int i = 10 ; |
L’assembleur fournit les directives correspondantes. Ici, on réserve un mot dans le segment de données et on donne sa valeur :
| .data i: .word 10 |
En cours de calcul on peut demander plus de mémoire au système d’exploitation qui sait étendre la zone de données du programme. Du point de vue du langage de programmation, on pensera à new de Pascal et Java, où à l’allocation mémoire implicite de Caml.
En SPIM, l’appel système numéro 9 prend la taille dans v0 et retourne le pointeur vers le début de bloc dans a0.
| # allouer a0 octets de mémoire. brk: # procédure d'allocation dynamique li $v0, 9 # appel système 9 syscall # alloue une taille a0 et j $ra # retourne le pointeur dans v0 |
En pratique, l’appel au système d’exploitation étant coûteux. On demande la mémoire au système par grosses quantités puis on satisfait les demandes dans les blocs ainsi préalloués. Un registre peut être utilisé pour contenir la première adresse libre.
| memsize = 1024*1024 __start: li $a0, memsize jal brk move $t8, $v0 # t8 réservé ... # allocation d'un tableau de a0 mots new_array: sw $a0, ($t8) # écrit la taille dans l'entête add $v0, $t8, 4 # v0 <- adresse de la case 0 add $a0, $a0, 1 # on alloue a0+1 mots mul $a0, $a0, 4 # en octets add $t8, $t8, $a0 # vraiment j $ra |
Ici, le code de lancement alloue une grosse zone de mémoire, tandis que la fonction new_array renvoie l’adresse d’une zone de mémoire allouée dans cette zone. L’argument a0 de new_array est la taille demandée (en mots), on remarque qu’en fait on alloue en fait a0+1 mots et que le premier mot alloué contient la taille du tableau. On ignore les problèmes de débordement et de libération de l’espace mémoire —qu’il conviendrait de traiter, par exemple en modifiant brk et en utilisant un glaneur de cellules (garbage collector) ou une déallocation explicite (dispose en Pascal).
On peut également, si on souhaite se simplifier la vie, allouer toute la zone de mémoire « dynamique » statiquement. Il devient alors impossible d’agrandir cette zone au cours de l’exécution. On aura alors le code de lancement :
| memsize = 1024*1024 cmemsize = 4 * memsize .data dynamique: .space cmemsize __start: la $t8, dynamique # t8 réservé ... |
Dans cette section je montre comment définir et utiliser une procédure simple, qui n’appelle pas d’autre procédure et prend des arguments peu nombreux.
Pour appeler une procédure, on utilise une l’instruction idoine
jal qui range l’adresse de code la suivant dans le registre
ra.
À la fin d’une procédure, on retournera à l’appelant en sautant à l’adresse
contenue dans ra.
Rappelons aussi que les arguments de la procédure sont
conventionnellement rangés dans certains registres
(ici de a0 à a3). En forçant un peu la note on remarque
que le registre ra est un argument supplémentaire.
Soit, par exemple, on définit une procédure writeln qui imprime un entier puis un retour à la ligne.
| .data # de la donnée nl: .asciiz "\n" # la chaîne "\n" .text # du code writeln: # l'argument est dans a0 li $v0, 1 # le numéro de print_int syscall # appel système li $v0, 4 # la primitive print_string la $a0, nl # la chaîne "\n" syscall j $ra # retour par saut à l'adresse ra |
Voici ensuite un programme simple qui utilise la procédure writeln pour afficher les entiers 1 et 2 :
| .text # du code .globl __start __start: li $a0, 1 # a0 <- 1 jal writeln # ra <- pc+1; saut à writeln li $a0, 2 # on recommence avec 2 jal writeln j Exit # saut à la fin du programme Exit: # fin du programme |
On remarque que, vu du programme principal, la procédure agit comme une instruction, (on l’exécute et on passe à la suivante). Il faut toutefois bien prendre garde à ce que la procédure utilise discrètement certains registres (ici le registre v0). Ainsi, si on souhaite afficher les entiers de 1 à 10 par une boucle, on ne pourra pas utiliser v0 comme compteur de boucle.
Les fonctions sont tout simplement des procédures qui rendent un résultat, ce résultat est rendu dans un registre conventionnel, ici v0. On écrira une fonction twice qui double son argument ainsi :
| .text twice: # l'argument est dans a0 add $v0, $a0, $a0 # v0 <- a0 + a0 j $ra |
On considère maintenant le cas le plus compliqué pour les procédures : le cas des procédures récursives, c’est à dire des procédures qui s’appellent elles-mêmes. L’exemple typique est celui de la fonction factorielle :
| function fact (n : integer) : integer ; begin if n <= 0 then fact := 1 else fact := n * fact (n-1) end ; |
Si nous traduisons ce code en suivant la convention de l’argument passé dans a0 et du résultat rendu dans v0 nous obtenons ce code :
| .text # a0 est n fact: ble $a0, $0, L1 # si a0 <= 0 aller en L1 sub $a0, $a0, 1 # argument de l'appel jal fact # v0 <- fact (n-1) mul $v0, $v0, $a0 # v0 <- n * v0 j $ra L1: li $v0, 1 j $ra |
Ce code est bien entendu incorrect,
l’erreur la plus visible concerne a0 dans le cas n > 0.
Après le jal fact, le registre a0 ne contient plus n.
De fait, il semble qu’il doivent contenir zéro.
Mais il y a une seconde erreur, un peu plus cachée :
le contenu du registre ra est détruit par l’instruction
jal fact et l’appel initial à fact ne retournera
jamais.
Graphiquement, on a la situation suivante :
| fn | ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ |
|
Où, au pire, on aura dans les n incarnations différentes de l’argument n et de l’adresse de retour.
Comme la fonction est récursive, il est vain de tenter de sauver les contenus de a0 et ra dans d’autres registres, l’appel récursif de fact détruira aussi les contenus de ces sauvegardes, car il exécutera le même code de sauvegarde. Il convient donc que chaque appel de fonction possède en propre un bout de mémoire, pour sauver le contenu des registres qui seront (ou risquent d’être) modifiés par l’appel récursif et dont les valeurs seront encore nécessaires (lues) au retour de l’appel. Cet espace est alloué sur la pile.
Par convention, la pile grossit vers les adresses décroissantes et le registre sp pointe vers le dernier mot utilisé.
Pour sauver un registre r sur la pile, on écrit :
| sub $sp, $sp, 4 # alloue un mot sur la pile sw r, 0($sp) # écrit r sur le sommet de la pile |
Pour restaurer un mot de la pile dans un registre r, on écrit :
| lw r, 0($sp) # lit le sommet de la pile dans r add $sp, $sp, 4 # désalloue un mot sur la pile |
En général, on alloue et désalloue l’espace en pile par blocs pour plusieurs sauvegardes à la fois. Ainsi, dans le cas de la factorielle, où il y a deux registres à sauvegarder, on commencera par réserver 2 mots en pile, et on oubliera pas de les rendre. Le code est modifié par une sauvegarde préalable des registres a0 et ra dans les registres t0 et t1, afin de mettre en vedette la sauvegarde des registres. En effet, les registres argument a0 et adresse de retour ra servent a communiquer entre le code qui appelle une fonction (l’appelant ou caller) et le code de la fonction (l’appelé ou callee) et toute discussion de leur sauvegarde manquera un peu de pureté. Bref, on obtient :
| .text # a0 est n fact: ble $a0, $0, L1 move $t0, $a0 # sauvegarde a0 -> t0 move $t1, $ra # sauvegarde ra -> t1 sub $a0, $t0, 1 sub $sp, $sp, 8 # réserver deux mots sw $t0, 0($sp) # sauvegarder t0 sw $t1, 4($sp) # sauvegarder t1 jal fact # car fact peut modifier t0 et t1 lw $t1, 4($sp) # restaurer t1 lw $t0, 0($sp) # restaurer t0 add $sp, $sp, 8 # rendre l'espace de pile mul $v0, $v0, $t0 # utilisation de t0 j $t1 # utilisation de t1 L1: li $v0, 1 j $ra |
Il faut noter qu’ici c’est l’appelant qui sauve les registres dont il sait avoir besoin et dont il pense qu’ils risquent d’être modifiés par un appel de procédure, c’est la convention dite caller save.
Il existe bien entendu la convention inverse (dite callee save), où l’appelé sauvegarde le contenu des registres dont il sait qu’il les modifie et dont il pense que l’appelant peut avoir encore besoin. Ici on obtiendra sensiblement le même code ! La différence essentielle est que les registres t0 et t1 sont cette fois sauvegardés avant d’être affectés.
| .text # a0 est n fact: ble $a0, $0, L1 sub $sp, $sp, 8 # réserver deux mots sw $t0, 0($sp) # sauvegarder t0 sw $t1, 4($sp) # sauvegarder t1 move $t0, $a0 move $t1, $ra sub $a0, $t0, 1 jal fact # au retour de fact t0 et t1 n'ont pas changé mul $v0, $v0, $t0 # utilisation de t0 move $ra, $t1 # utilisation de t1 lw $t1, 4($sp) # restaurer t1 lw $t0, 0($sp) # restaurer t0 add $sp, $sp, 8 # rendre l'espace de pile j $ra L1: li $v0, 1 j $ra |
Évidemment, s’il s’agit de coder la fonction factorielle en assembleur, on se passera des sauvegardes en registres et on écrira plus directement :
| fact: blez $a0, fact_0 # si a0 <= 0 saut à fact_0 sub $sp, $sp, 8 # réserve deux mots en pile sw $ra, 0($sp) # sauve l'adresse de retour sw $a0, 4($sp) # et la valeur de a0 sub $a0, $a0, 1 # décrémente a0 jal fact # v0 <- appel récursif (a0-1) lw $a0, 4($sp) # récupère a0 mul $v0, $v0, $a0 # v0 <- a0 * v0 lw $ra, 0($sp) # récupère l'adresse de retour add $sp, $sp, 8 # libère la pile j $ra # retour à l'appelant fact_0: li $v0, 1 # v0 <- 1 j $ra # retour à l'appelant |
Les quelques exemples de programmation assembleur que nous avons vus sont typiques de la programmation assembleur à la main. Dans ce contexte et pour des programmes courts, il est assez facile de bien se servir des registres et donc de produire des programmes relativement efficaces.
Il est toutefois important de connaître le principe de techniques plus simples d’utilisation de la pile.
Dans un modèle simple, il n’y a que quelques registres spécialisés, et entre autres un pointeur de pile sp.
On se donne parfois un registre supplémentaire, l’accumulateur que l’on peut voir comme le sommet de la pile du modèle précédent. Ainsi une addition range la somme de l’accumulateur et d’une valeur dépilée dans l’accumulateur.
Sans développer exagérément, la fonction twice, qui double son argument, écrite selon ces idées donnera ceci :
| #l'accumulateur est v0, on dispose de quelques registres twice: # l'argument n est 0(sp), le retour 4(sp) lw $v0, 0($sp) # accu <- n sub $sp, $sp, 4 # empiler sw $v0, 0($sp) lw $v0, 4($sp) # accu <- n lw $t0, 0($sp) # dépiler add $sp, $sp, 4 add $v0, $v0, $t0 # addition add $sp, $sp, 4 # dépiler l'argument lw $ra, 0($sp) # dépiler adresse de retour add $sp, $sp, 4 j $ra # retour |
Code qui peut paraître abscons, mais qui devient peut être plus compréhensible comme expansion simple du bytecode (Caml) suivant :
| twice: acc 0 push acc 1 addint return 1 |
Il est maintenant temps de revenir sur les noms symboliques des registres (voir section 2.2.2).
En général:
sub $v0,$zero,$v0) et de l’instruction
de transfert de registre à registre (add $v1,$zero,$v0).
Le format des instructions que le processeur décode en dernière
analyse en est simplifié.
Rappelons, que sauf pour pour zero, ra, k0 et k1 (voire at) on peut ne pas suivre ces conventions. Mais alors on est tout seul, on ne peut pas interagir avec le monde extérieur.
Il est bien connu dans les milieux de la « vraie programmation » que la pile « c’est mal ». En fait, c’est la récursion qui est visée, et effectivement il peut arriver qu’un programme par ailleurs réputé correct en théorie échoue par épuisement de la mémoire, phagocytée par la pile des nombreux appels en cours.
Mais, si la récursion est interdite (et elle l’était dans les vieilles versions de Fortran), alors on peut tout simplement allouer l’espace nécessaire à une fonction dans le segment des données statiques, c’est à dire, lors de la compilation. Dès lors, il n’y a plus aucun risque d’épuisement de la mémoire à l’exécution du fait des appels de fonctions. Mieux, l’ensemble des rapports entre les fonctions peut être assez facilement connu du compilateur et les conventions d’utilisation des registres adaptées en conséquence.
Ce point de vue est en voie d’extinction, en raison de l’expressivité de la récursion et de l’augmentation de la taille des mémoires. Mais la pile peut toujours déborder, bien évidemment.