Previous Up Next

Chapitre 2  Code machine

2.1  Les processeurs

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.

2.1.1  Un peu de culture : le bytecode

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.

2.2  Description d’un processeur

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

2.2.1  La mémoire

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 :

 Stack
 
  
 
 Données
 allouées dynamiquement
 Données statiques
 modifiables
 Texte (programme)
 non écrivable
 Réservé au système

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.

2.2.2  Les registres

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.

NomNuméroUsage
zero0Zéro (toujours)
at1Réservé par l’assembleur
v0 .. v12 .. 3Retour de valeurs
a0 .. a34 .. 7Passage d’arguments
t0 .. t78 .. 15Temporaires non sauvegardés
s0.. s716 .. 23Temporaires sauvegardés
t8.. t924 .. 25Temporaires non sauvegardés
k0.. k126 .. 27Réservés par le système
gp28Global Pointer
sp29Stack Pointer
fp30Frame Pointeur
ra31Return Address

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.

2.2.3  Le jeu d’instructions

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édiatun entier
Directle contenu du registre
Indirectle 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.

nune constante entière
lune étiquette (adresse)
 
rnom de registre
aabsolu (n ou l)
oopérande (r ou a)

La plupart des instructions suivent le modèle

Les instructions qui interagissent avec la mémoire sont uniquement les instructions load et store.

Les instructions de contrôle conditionnel ou inconditionnel:

Voici la liste des principales instructions :

SyntaxeEffet
move r1, r2r1r2
add r1, r2, or1o + r2
sub r1, r2, or1r2o
mul r1, r2, or1r2 × o
div r1, r2, or1r2 ÷ o
and r1, r2, or1r2 land o
or r1, r2, or1r2 lor o
xor r1, r2, or1r2 lxor o
sll r1, r2, or1r2 lsl o
srl r1, r2, or1r2 lsr o
li r1, nr1n
la r1, ar1a
 
SyntaxeEffet
lw r1, o (r2)r1tas.(r2 + o)
sw r1, o (r2)r1tas.(r2 + o)
slt r1, r2, or1r2 < o
sle r1, r2, or1r2o
seq r1, r2, or1r2 = o
sne r1, r2, or1r2o
j opco
jal orapc+1 ∧ pco
beq r, o, apca si r = o
bne r, o, apca si ro
syscallappel système
nopne fait rien

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.

2.2.4  Les appels systèmes

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:

NomNoEffet
print_int1imprime l’entier contenu dans a0
print_string4imprime la chaîne en a0 jusqu’à ’\000’
read_int5lit un entier et le place dans v0
sbrk9alloue a0 octets dans le tas,
  retourne l’adresse du début dans v0.
exit10arrêt du programme en cours d’exécution

2.3  Langage assembleur et langage machine

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.

2.3.1  Pseudo-Instructions

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.

AssembleurLangage machineCommentaire
blt r, o, a slt $1r, oJustifie le registre at ($1)
  bne $1$0aréservé par l’assembleur.
li $t0, 400020 lui $1, 6charge les 16 bits de poids fort
  ori $8$1, 6804puis les 16 bits de poids faible
add $t0$t1, 1 addi $8$9, 1addition avec une constante
move $t0$t1 addu $8$0$9addition “unsigned” avec zéro

Pour voir, essayez :

% spim -notrap -file hello.spi

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$t1trois correspond deux instructions machine, slt $1$8$9 et bne $1$0, 12 [trois-0x00400004].

2.4  Exemples de programmes en assembleur

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.

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).

2.4.1  Conditionnelle

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

2.4.2  Boucles

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
While: if t1 <= 0 then goto End else begin t2 := t2 + t1; t1 := t1 - 1; goto While end; End:
 Code Mips
While: ble $t1, $0, End add $t2, $t2, $t1 sub $t1, $t1, 1 j While End:

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.

2.4.3  Expressions arithmétiques

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

2.4.4  Les données

Données statiques

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

Allocation dynamique

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é ...

2.4.5  Procédures simples

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

2.4.6  Procédures compliquées

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







a0 ← a0 −1 
   fn−1 



       a0 ← a0 − 1  
       … 
       v0 ← v0 × a0 
       
v0 ← v0 × a0 

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.

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

Utilisation simple de la pile

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

Conventions d’appel

Il est maintenant temps de revenir sur les noms symboliques des registres (voir section 2.2.2).

En général:

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.

Un peu de culture

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.


Previous Up Next