3MMCEP TP Intro

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)


Laptop.png  Première Année  CDROM.png  Informatique 
Fleche haut.png

Le but de la partie « Exploitation des Processeurs » est de fournir à tout futur ingénieur Ensimag une compréhension générale des mécanismes bas-niveau (dans le sens « proches de la machine ») mis en œuvre dans la plupart des systèmes actuels, du point de vue du logiciel (la partie Projet de Conception des Processeurs prend quant à elle le point de vue du matériel).

Plus précisément, on étudiera notamment dans cette partie :

  • comment un compilateur produit du code assembleur à partir d'un programme écrit dans un langage de haut-niveau (dans notre cas le langage C, qui présente l'avantage d'être beaucoup plus proche de l'assembleur qu'un langage comme Ada par exemple) ;
  • la structure d'une unité d'exécution (processus) en termes de gestion de zone mémoires (code, données statiques, tas, pile) ;
  • les interactions entre un programme et son environnement d'exécution (utilisation d'une bibliothèque de fonctions, conventions de gestion des registres et de la mémoire, etc).

Le but de cette partie n'est surtout pas d'apprendre à écrire de gros programmes directement en assembleur, ce qui n'aurait en pratique que peu d'intérêt. Il constitue plutôt une introduction à des notions de base de la programmation système et de l'écriture de compilateurs, qui seront approfondies en 2A.

Introduction

Le but de cette séance est de découvrir l'architecture x86_64 que l'on va utiliser ce semestre pour écrire du code assembleur. On n'écrira pas de code MIPS dans la partie Exploitation des Processeurs, par contre vous devrez en écrire pour tester le processeur développé dans la partie Projet de Conception de Processeurs. Si vous souhaitez tester vos programmes MIPS dans un environnement convivial, vous pouvez utiliser le simulateur SPIM gratuit.

Le x86_64 est une architecture à jeu d'instructions complexe (CISC en anglais, par opposition aux processeurs RISC plus courants) : cela signifie qu'il supporte beaucoup d'instructions, dont certaines sont capables d'effectuer des opérations très complexes. Dans le cadre de ce cours, on n'utilisera qu'un tout petit sous-ensemble du jeu d'instruction supporté par le processeur.

Le choix de l'architecture x86_64 par rapport au MIPS est une conséquence des différences entre les modèles RISC et CISC : un processeur RISC (comme le MIPS) offre un jeu d'instruction idéal pour l'écriture d'un compilateur qui génère du code de façon systématique, mais écrire du code RISC « à la main » peut devenir rapidement fastidieux. A-contrario, l'architecture x86_64 offre des instructions puissantes qui simplifient l'écriture de programmes à la main.

Rappels de cours

Le langage assembleur

L'assembleur est le langage compréhensible par un humain qui se situe le plus prêt de la machine.

Le processeur exécute des instructions écrites en binaire comme vous l'avez vu dans le cours d'Architecture des ordinateurs. Il est très difficile pour un humain de se souvenir que la séquence 01001000110001111100000000000101000000000000 copie la valeur 5 dans un registre appelé %rax. C'est pour cela qu'on utilise l'assembleur, qui est représentation textuelle des instructions supportées par le processeur : dans le cas de cet exemple, on écrira movq $5, %rax, ce qui est nettement plus clair.

L'assembleur est un langage sans structure de contrôle (i.e. pas de if, while, etc.) dont chaque instruction peut-être traduite directement dans la séquence binaire équivalente compréhensible par le processeur. Le logiciel qui réalise cette traduction s'appelle aussi un assembleur. Il en existe beaucoup supportant l'architecture x86_64 : on utilisera l'assembleur GAS qui est l'assembleur intégré à GCC.

Le processeur

Le premier processeur supportant l'architecture x86_64 (aussi connue sous le nom d'AMD64 du nom du fabricant de ce premier processeur) est sorti en 2003 et présente la propriété d'être compatible avec les processeurs Pentium (1993), 80386 (1985) et 8086 (1978). Cette compatibilité ascendante explique en partie la complexité de l'architecture x86_64.

L'architecture x86_64 est une architecture « 64 bits » : cela signifie que le mot de donnée de base et les adresses en mémoire sont codés sur 8 octets.

Les processeurs conforment à cette architecture contiennent seulement 14 registres généraux (pouvant donc être utilisés librement pour effectuer des calculs) sur 64 bits (les processeur RISC en ont généralement beaucoup plus). Ces registres ont la particularité de pouvoir être fractionnés en sous-registres de taille 32, 16 ou 8 bits.

Par exemple, le registre %rax est un registre 64 bits mais :

  • les 32 bits de poids faibles (i.e. les bits 31..0) de ce registre sont accessibles directement en utilisant le nom %eax ;
  • les 16 bits de poids faibles (i.e. les bits 15..0) sont accessibles grâce au nom %ax ;
  • et les 8 bits de poids faibles (i.e. les bits 7..0) sont accessibles par le nom %al.

Il s'agit d'un héritage des processus 80386 (processeur 32 bits) et 8086 (processeur 16 bits). Attention, pour ceux qui connaissent l'architecture Pentium, les noms de registres %ah, %bh, %ch et %dh ne doivent plus être utilisés dans les programmes x86_64.

Il est important de comprendre qu'il s'agit bien du même registre 64 bits : simplement certaines parties de ce registre portent des noms spécifiques. Ainsi, par exemple :

  • si on copie une valeur 64 bits dans %rax, tout le registre sera modifié ;
  • si on copie une valeur 32 bits dans %eax, les bits 31..0 de %rax seront modifiés et les bits 63..32 ne changeront pas ;
  • si on copie une valeur 16 bits dans %ax, les bits 15..0 de %rax seront modifiés et les bits 63..16 ne changeront pas ;
  • si on copie une valeur 8 bits dans %al, les bits 7..0 de %rax seront modifiés et les bits 63..8 ne changeront pas.

Le schéma ci-dessous illustre l'emboitement des registres %rax, %eax, %ax et %al :

3MM1LDB rax.png

Le même schéma se retrouve pour les autres registres du processeur :

  • %rbx (64 bits) se découpe en %ebx (32 bits), %bx (16 bits) et %bl (8 bits) ;
  • %rcx (64 bits) se découpe en %ecx (32 bits), %cx (16 bits) et %cl (8 bits) ;
  • %rdx (64 bits) se découpe en %edx (32 bits), %dx (16 bits) et %dl (8 bits) ;
  • %rsi (64 bits) se découpe en %esi (32 bits), %si (16 bits) et %sil (8 bits) ;
  • %rdi (64 bits) se découpe en %edi (32 bits), %di (16 bits) et %dil (8 bits).

Les 8 autres registres généraux portent des noms plus réguliers :

  • %r8 (64 bits) se découpe en %r8d (32 bits), %r8w (16 bits) et %r8b (8 bits) ;

...

  • %r15 (64 bits) se découpe en %r15d (32 bits), %r15w (16 bits) et %r15b (8 bits).

Il existe enfin d'autres registres dont on détaillera l'intérêt plus loin :

  • %rsp est le pointeur de sommet de pile et %rbp le pointeur de cadre de pile : ces registres seront présentés en détail lorsque l'on apprendra à écrire des fonctions en assembleur x86_64 ;
  • %rip est le compteur-programme (le PC de vos cours d'architecture) : il ne peut pas être modifié directement, à part par des instructions de saut ;
  • %rflags est le registre des indicateurs (qui contient par exemple les indicateurs C et Z que vous avez vu au premier semestre en architecture), lui aussi ne peut pas être manipulé directement.

Ces différents registres seront toujours manipulés sur 64 bits.

La mémoire

Les adresses sont codées sur 64 bits : la taille maximale de la mémoire adressable est donc 2^{64} = 18 446 744 073 709 551 616 soit environ 18 milliards de milliards de cases mémoire. Il s'agit bien sûr d'une limite théorique : il n'existe pas encore de machine disposant d'autant de mémoire !

Le bus de données est aussi sur 64 bits, mais on peut accéder à des données sur 64, 32, 16 et 8 bits : on devra donc systématiquement préciser la taille des données manipulées.

L'architecture x86_64 est conçue pour des processeurs little-endian, ce qui signifie que dans un mot mémoire, les bits de poids faibles sont stockés en premier. Par exemple, si la valeur (sur 64 bits) 0x1122334455667788 est stockée à l'adresse 0x1000, on trouve en mémoire :

Adresses 0x1000 0x1001 0x1002 0x1003 0x1004 0x1005 0x1006 0x1007
Valeurs 0x88 0x77 0x66 0x55 0x44 0x33 0x22 0x11

Programmation en assembleur x86_64

L'architecture x86_64 implante plusieurs centaines d'instructions. Certaines de ces instructions sont capables de réaliser des opérations très puissantes, comme par exemple effectuer des calculs mathématiques complexes en une seule opération. Dans le cadre de ce cours, on n'utilisera qu'un sous-ensemble très restreint des instructions fournies.

L'instruction de copie

mov src, dst copie une valeur d'un endroit à un autre, spécifiquement :

  • d'un registre à un autre ;
  • d'un registre vers la mémoire (store) ;
  • de la mémoire vers un registre (load) ;
  • une constante dans un registre (move immediate) ;
  • et même une constante vers la mémoire.

Il n'est par contre pas possible de copier une valeur de la mémoire vers un autre endroit en mémoire : cette restriction est valable pour la quasi-totalité des instructions x86_64, qui ne pourront jamais avoir deux opérandes en mémoire.

Comme on l'a vu, l'architecture x86_64 permet de manipuler des données sur 64, 32, 16 ou 8 bits : on doit donc spécifier systématiquement la taille des données manipulées, en utilisant des suffixes de taille, qui seront collés à la fin de l'instruction :

  • q est le suffixe pour une donnée sur 64 bits : movq %rax, %r10 copie les 64 bits de %rax dans les 64 bits de %r10 ;
  • l est le suffixe pour une donnée sur 32 bits : movl $0x12345678, %eax charge la constante hexadécimale 0x12345678 dans le registre 32 bits %eax ;
  • w est le suffixe pour une donnée sur 16 bits : movw %ax, a(%rip) copie le contenu du registre 16 bits %ax dans la variable 16 bits nommée a (on comprendra plus tard la notation a(%rip)) ;
  • b est le suffixe pour une donnée sur 8 bits : movb $15, b(%rip) copie la valeur 15 dans la variable 8 bits nommée b.

Il est indispensable d'utiliser les suffixes de taille lorsqu'on écrit du code x86_64 : si on ne le fait pas (et qu'on écrit par exemple mov au lieu de movq, movl, etc.), c'est l'assembleur qui choisira la taille des données manipulée (en fonction de ce qui lui semble « logique ») mais il n'est pas sûr qu'il choisisse celle que l'on sous-entendait, et on risque de se retrouver avec une erreur très difficile à localiser.

Opérations arithmétiques

Il existe de nombreuses opérations arithmétiques, dont on détaille les plus courantes :

  • Addition : add
  • Soustraction : sub
  • Négation : neg
  • Décalage à gauche : shl décale une valeur d'un nombre de bits N compris entre 1 et 63, en complétant avec des 0 à droite (ce qui revient à multiplier la valeur initiale par 2^N)
  • Décalage arithmétique à droite : sar décale une valeur d'un nombre de bits N compris entre 1 et 63, en complétant avec le bit de signe à gauche (ce qui revient à diviser la valeur initiale par 2^N si cette valeur est un entier signé)
  • Décalage logique à droite : shr décale une valeur d'un nombre de bits N compris entre 1 et 63, en complétant avec des 0 à gauche (ce qui revient à diviser la valeur initiale par 2^N si cette valeur est un entier naturel)
  • Conjonction logique : and
  • Disjonction logique inclusive : or
  • Disjonction logique exclusive : xor
  • Négation logique : not

Comparaisons

On utilise les comparaisons avant un branchement conditionnel, pour implanter un if ou un while :

  • Comparaison arithmétique : cmp, par exemple cmpq $5, %rax compare %rax avec 5, en effectuant la soustraction %rax - 5 sans stocker le résultat ;
  • Comparaison logique : test, par exemple testb $0x01, %bl effectue un et bit-à-bit entre la constante 1 et %bl, sans stocker le résultat.

Les comparaisons ne stockent pas le résultat de l'opération effectuée, mais mettent à jour le registre des indicateurs %rflags, qui est utilisé par les branchements conditionnels.

Branchements

Le branchement le plus simple est le branchement inconditionnel : jmp destination.

Pour préciser la destination d'un branchement, on utilise une étiquette :

    movq $0, %rax
    jmp plus_loin
    movq $5, %r10
plus_loin:
    addq $10, %rax

Pour implanter des if et while, on utilise les branchements conditionnels, qui se basent sur l'état d'un ou plusieurs indicateurs contenus dans le registre %rflags pour déterminer si le saut doit être effectué ou pas :

  • je etiq saute vers l'étiquette etiq ssi la comparaison a donné un résultat « égal » ;
  • jne etiq saute ssi le résultat était différent (not equal) ;

Les indicateurs à tester sont parfois différents selon si on travaille sur des entiers signés ou naturels. Pour les naturels, on utilisera :

  • ja etiq saute ssi le résultat de la comparaison était strictement supérieur (jump if above) ;
  • jb etiq saute ssi le résultat de la comparaison était strictement inférieur (jump if below) ;

Et pour les entiers signés :

  • jg etiq saute ssi le résultat de la comparaison était strictement supérieur (jump if greater) ;
  • jl etiq saute ssi le résultat de la comparaison était strictement inférieur (jump if less) ;

On peut composer les suffixes, et obtenir ainsi plusieurs mnémoniques différents pour la même instruction : jna (jump if not above) est strictement équivalent à jbe (jump if below or equal).

Le tableau ci-dessous résume les différents branchements conditionnels qu'on utilisera :

Branchements conditionnels
Comparaison Entiers naturels Entiers signés
> ja, jnbe jg, jnle
jae, jnb jge, jnl
< jb, jnae jl, jnge
jbe, jna jle, jng
= je, jz
jne, jnz

On trouvera dans cet extrait de la documentation Intel la liste exhaustive de tous les branchements conditionnels existants.

Traduction systématiques des structures de contrôle classiques

On peut traduire les structures de contrôles des langages de haut-niveau de façon très systématique, ce qui réduit le risque d'erreur. Dans le cadre de ce cours, on demandera toujours de traduire systématiquement les algorithmes donnés en C, sans chercher à « optimiser » le code (sauf indication contraire).

Structure d'un if

Soit par exemple le code C suivant, où x est une variable globale de type (u)int64_t initialisée auparavant :

if (x == 5) {
    x = x + 2;
} else {
    x = x – 4;
}

Le code assembleur correspondant prendra toujours la forme ci-dessous :

if:
    cmpq $5, x(%rip)
    jne else
    addq $2, x(%rip)
    jmp fin_if
else:
    subq $4, x(%rip)
fin_if:

On expliquera à la prochaine séance la signification de la notation x(%rip) : pour l'instant, il suffit de comprendre que c'est comme cela qu'on peut accéder à la variable globale x dans un programme en assembleur.

Structure d'une boucle while

On suppose dans le programme ci-dessous que x est une variable de type int64_t déclarée globalement et initialisée auparavant :

while (x > 5) {
    x = x - 1;
}

Le type de x impose d'utiliser le bon branchement conditionnel dans le code assembleur :

while:
    cmpq $5, x(%rip)
    jle fin_while
    subq $1, x(%rip)
    jmp while
fin_while:

Structure d'une boucle for

Même supposition pour x que dans le programme précédent, et on suppose aussi que i est une variable globale de type uint64_t non-initialisée :

for (i = 0; i < 5; i ++) {
    x = x + 4;
}

Le code aura une forme similaire à celle d'un while :

    movq $0, i(%rip)
for:
    cmpq $5, i(%rip)
    jae fin_for
    addq $4, x(%rip)
    addq $1, i(%rip)
    jmp for
fin_for:

Représentation d'un programme en mémoire

Principe général

Lorsqu'on compile ou assemble un programme, on obtient un fichier binaire contenant le code de ce programme en langage machine, ainsi que les données dont il aura besoin à l'exécution. Ce fichier binaire respecte un certain format, dont ELF et Mach-O par exemple.

Lorsqu'on lance l'exécution de ce programme (en tapant ./mon_prog dans un terminal par exemple), le fichier binaire est chargé en mémoire et un certain nombre d'opérations dépassant le cadre de ce cours sont effectuées afin de rendre le programme exécutable. Ce qui nous intéresse ici est la représentation finale du programme dans la mémoire, juste avant que le processeur commence à exécuter son code machine.

On parle traditionnellement de processus pour désigner un programme en cours d'exécution dans la mémoire du système. De façon volontairement simplifiée, un processus a en mémoire la structure suivante :

3MM1LDB processus.png

Lorsqu'on écrit un programme en C, on ne se préoccupe pas de savoir dans quelle zone du processus va se retrouver telle fonction ou telle donnée : c'est le travail du compilateur. Mais lorsqu'on écrit du code assembleur, on doit définir précisément la structure du programme. On utilise pour ça des directives, qui sont des commandes qui ne font pas partie du langage assembleur mais qui aide le programme d'assemblage à faire son travail.

La zone text

Cette zone contient le code en langage machine de toutes les fonctions du programme. Lorsqu'on écrit de l'assembleur, on est par défaut dans cette zone. Si l'on souhaite le préciser explicitement, on peut utiliser la directive .text avant de commencer à écrire du code assembleur, comme par exemple dans le code ci-dessous :

/*
void fct(void)
{
    // du code...
}
*/
    .text
fct:
    // du code...

La zone data

Structure de la zone

Cette zone contient les données allouées statiquement dans le programme, c'est à dire les variables globales du langage C. En pratique, cette zone est souvent découpées en sous-zones, mais ce découpage est très dépendant de l'architecture de destination. On trouve souvent :

  • la zone data a proprement parler qui contient les données initialisées modifiables ;
  • la zone rodata qui contient des données en lecture seule (read-only) ;
  • la zone bss qui contient des données modifiables mais non-initialisées.

Par exemple, dans le programme C ci-dessous :

int64_t x = 5;

int64_t y;

void fct(void)
{
    printf("toto");
}
  • la variable globale x sera placée dans la zone data ;
  • la variable globale y sera placée dans la zone bss ;
  • la chaine de caractères constante "toto" sera (parfois) placée dans la zone rodata.

En pratique, l'utilisation de la zone rodata est facultative : on ne l'utilisera pas dans le cadre de ce cours, et on placera toutes les données initialisées dans la zone data.

La zone bss quant à elle est souvent utilisé, mais la directive permettant de la désigner dépend du système. On s'en servira principalement pour réserver de la place mémoire lors de la définition de tableaux (dans le cadre de l'exemple C ci-dessus, on pourrait aussi bien placer y en zone data et l'initialiser à 0 par exemple).

Note : sur beaucoup de systèmes, la zone bss est initialisée à 0 avant le début de l'exécution du programme, mais en toute rigueur on ne doit pas compter sur ce point car ce n'est pas toujours le cas.

La directive assembleur permettant de signifier le début de la zone data est tout simplement .data. Si l'on veut réserver de l'espace mémoire dans la zone bss, on utilisera la directive .comm dont on définira la syntaxe plus bas.

Directive de « typage »

En assembleur, pas plus que dans la mémoire physique de la machine, il n'existe pas de types de données à proprement parler. On travaille toujours en termes d'espace mémoire réservé pour les variables : on ne sait pas si x est un entier ou un réel, on sait juste que cette variable occupe 8 octets en mémoire. En pratique, on n'utilisera que des entiers, des tableaux d'entiers et des chaines de caractères dans ce cours.

Dans la zone data du programme, on utilise fréquemment les directives suivantes pour réserver de l'espace pour les variables globales du programme :

  • .quad val permet de réserver 8 octets consécutifs de mémoire et de les initialiser avec la valeur val ;
  • .long val permet de réserver 4 octets consécutifs de mémoire et de les initialiser avec la valeur val ;
  • .short val permet de réserver 2 octets consécutifs de mémoire et de les initialiser avec la valeur val ;
  • .byte val permet de réserver 1 octet de mémoire et de l'initialiser avec la valeur val ;
  • .ascii "chaine" réserve autant d'octets consécutifs de mémoire qu'il y a de caractères dans la chaine et les initialise avec les caractères de la chaine ;
  • .asciz "chaine" est similaire à .ascii mais ajoute en plus le caractère '\0' à la fin de la chaine : cette directive permet donc de traduire directement les chaines de caractères du C.

Les directives ci-dessus permettent de réserver de l'espace mémoire pour les différentes variables du programme. Mais pour pouvoir les utiliser, on doit pouvoir les nommer : on utilise pour cela des étiquettes, comme pour les fonctions.

Soit par exemple la zone data d'un programme assembleur quelconque :

    .data
t:  .quad 0x1122334455667788
x:  .long 0x12345678
y:  .short 20000
z:  .byte 0xFF
c:  .ascii "a"
ch: .asciz "toto"

.comm tab, 10 * 4

Dans cet exemple, on trouve :

  • une variable globale t qui représente un entier sur 8 octets valant initialement la valeur hexadécimale 0x1122334455667788 ;
  • une variable globale x qui représente un entier sur 4 octets valant initialement 0x12345678 ;
  • une variable globale y qui représente un entier court (2 octets) valant initialement 20000 ;
  • une variable globale z qui représente un octet valant initialement 0xFF (c'est à dire aussi bien -1 que 255 selon si on considère cet octet comme signé ou non) ;
  • un caractère isolé c qui vaut initialement 'a' ;
  • une chaine de caractère ch qui contient initialement les caractères 't', 'o', 't', 'o', '\0'.

On voit aussi que la directive comm, qui permet de réserver de la place pour des données non-initialisées, a une syntaxe légèrement différente : on indique d'abord la directive, puis ensuite l'étiquette suivie de la place à réserver après une virgule. Ici, on réserve 40 octets à partir d'une étiquette appelée tab : on est donc vraisemblablement en train d'allouer un tableau de 10 entiers (sur 4 octets chacun). L'assembleur est capable d'effectuer des opérations arithmétiques simples, on peut s'en servir pour rendre le code plus clair.

Correspondance entre les types du C et de l'assembleur

Le langage C définit des types entiers « classiques » comme int, long, short, etc. L'inconvénient de ces types est que leur taille peut dépendre de l'architecture sous-jacente. Pour éviter ce problème, on utilisera les types de tailles fixes définis dans inttypes.h et que vous avez dû voir pendant la semaine d'introduction au C. On donne ci-dessous la correspondance entre les types du C et les directives assembleur à utiliser dans la zone .data :

Types du C / Directives x86_64
Type C99 Taille en octets Directive x86_64
int64_t, uint64_t 8 .quad
int32_t, uint32_t 4 .long
int16_t, uint16_t 2 .short
int8_t, uint8_t 1 .byte
char 1 .ascii
pointeurs (tous) 8 .quad

Le tas

Le tas (heap en anglais) est la zone dans laquelle les fonctions malloc et calloc prennent la mémoire à réserver dynamiquement quand on les appelle. Cette zone a en général une taille prédéfinie lors de la création du processus et peut potentiellement grandir grace à un mécanisme appelé « mémoire virtuelle » que vous étudierez dans le cours de système en 2A.

La pile

La pile (stack en anglais) d'exécution est la zone dans laquelle on stocke notamment les variables locales aux différentes fonctions du programme (on rappelle que la zone data ne contient que les variables globales). Cette zone est organisé comme une pile (au sens algorithmique du terme), et part donc de la fin de l'espace mémoire du processus pour remonter vers le début à chaque fois que l'on empile des valeurs.

La pile a une taille fixe qui est généralement une constante dépendant du système utilisé. A noter que dans de nombreux systèmes, on ne vérifie pas que l'on n'empile pas plus de données qu'il n'y a d'espace réservé pour la pile, et on peut parfaitement arriver à écraser d'autres données, ou même du code, si on en empile trop : on parle alors de « débordement de pile » (stack overflow en anglais), une technique couramment utilisée pour exploiter des failles de sécurité dans les systèmes.

On verra plus tard dans ce cours comment on peut utiliser des variables locales et gérer la pile d'exécution.

Etude d'un exemple : le PGCD

Récupérez les sources fournies dans cette archive et décompressez-la pour extraire les fichiers. Ouvrez le fichier fct_pgcd.s qui contient le code assembleur de la fonction PGCD.

Soit le programme en C ci-dessous qui calcule le PGCD de a et b, deux variables globales de type uint32_ définies par exemple dans le programme principal :

uint32_t pgcd(void)
{
    while (a != b) {
        if (a < b) {
            b = b - a;
        } else {
            a = a - b;
        }
    }
    return a;
}

En assembleur, on traduit ce code comme suit :

    .text
    .globl pgcd
pgcd:
    enter $0, $0
    // while (a != b) {
while:
    movl a(%rip), %eax
    cmpl b(%rip), %eax
    je fin_while
    // if (a < b) {
    movl a(%rip), %eax
    cmpl b(%rip), %eax
    // jmp ssi not(a < b)
    jnb else
    // b = b - a;
    movl a(%rip), %eax
    subl %eax, b(%rip)
    jmp fin_if
else:
    // a = a - b:
    movl b(%rip), %eax
    subl %eax, a(%rip)
fin_if:
    jmp while
fin_while:
    // return a;
    movl a(%rip), %eax
    leave
    ret

Point d'entrée et étiquettes publiques

Le programme commence par la directive .globl qui est liée à la déclaration de l'étiquette pgcd :

    .globl pgcd
pgcd:

Par défaut, toutes les étiquettes déclarées dans un programme assembleur sont privées et invisibles à l'extérieur du fichier. Or la fonction pgcd doit être visible pour pouvoir être appelée par le programme principal. C'est le but de directive .globl qui rend l'étiquette pgcd publique.

En-tête et fin de fonction

enter $0, $0
...
leave
...

Toutes les fonctions que l'on écrira en assembleur commencent par l'instruction enter et se terminent par l'instruction leave : on comprendra plus tard à quoi servent ces instructions.

Valeur renvoyée

movl a(%rip), %eax
ret

Par convention, une fonction en assembleur renvoie sa valeur de retour dans le registre %rax, ou une de ses fractions si on renvoie une valeur de taille inférieure à 64 bits (ici, on renvoie un entier sur 32 bits, donc on utilise %eax). Si on écrit une fonction qui ne renvoie rien (void), il suffit de ne rien copier dans %rax : son contenu sera de toute façon ignoré par la fonction appelante.

L'instruction ret est l'équivalent du return en C et en Ada, et rend la main à la fonction appelante (ici, le système).

Déclaration des variables

Les variables globales a et b sont déclarées dans le programme principal, mais elles sont accessibles depuis le code assembleur (en C, tous les symboles sont publics sauf s'ils sont explicitement rendus privés par la directive static). On peut donc y accéder exactement comme si elles étaient définies dans la zone .data du fichier assembleur.

Exercices

On verra plus tard qu'il existe des conventions d'utilisation des registres : on ne peut pas utiliser n'importe-quel registre n'importe-comme si on veut interfacer les programmes assembleur avec du C. Dans tous les exercices ci-dessous vous n'utiliserez que les registres %rax (64 bits), %eax (32 bits) et %al (8 bits) pour vos valeurs temporaires (vous n'avez pas besoin de plus d'un registre pour ces exercices).

Utilisation de GDB pour la mise au point de programmes assembleur

Le fichier pgcd.c contient un programme principal écrit en C qui permet de lire les valeurs initiales de a et b et qui appelle la fonction PGCD écrite en assembleur dans le fichier fct_pgcd.s.

Vous pouvez compiler ces deux fichiers et créer le binaire en tapant simplement : make pgcd.

On va utiliser GDB pour tracer l'exécution du programme instruction par instruction :

  • charger le programme dans GDB en tapant gdb ./pgcd ;
  • ajouter un point d'arrêt au début de la fonction PGCD en utilisant la commande break pgcd ;
  • afficher les valeurs des variables a et b en utilisant les commandes display a et display b : l'affichage ne se fera que lors de l'exécution suivante ;
  • faites de même pour afficher le contenu du registre %eax : display $eax (attention, c'est bien le signe $ qu'il faut utiliser devant le nom du registre, et pas un %) ;
  • lancer l'exécution en tapant run 15 10 : noter que l'exécution s'arrête sur le point d'arrêt positionné sur pgcd : GDB affiche alors la prochaine instruction à exécuter (i.e. elle n'a pas encore été exécutée) ;
  • continuer l'exécution du programme pas à pas avec la commande step en vérifiant les valeurs des variables et du registre après l'exécution de chaque instruction qui les modifie ;
  • vérifier qu'on saute bien vers else la première fois qu'on exécute l'instruction jnb else mais pas la deuxième ;
  • vérifier aussi qu'on fait bien deux itérations de la boucle while avant d'en sortir (i.e. le branchement conditionnel je fin_while n'est pas effectué lors des deux premières itérations) ;
  • vérifier que le PGCD (5) est bien dans %eax à la fin de la fonction, juste avant d'exécuter l'instruction ret ;
  • ensuite on peut terminer proprement l'exécution du programme en tapant continue.

On fournit un aide-mémoire pour gdb qui contient beaucoup plus d'information que ce qui vous sera nécessaire ce semestre.

Somme des 10 premiers entiers

Traduire en assembleur de façon systématique le code C suivant qui calcule la somme des 10 premiers entiers naturels. Vous écrirez le code assembleur dans le fichier fct_somme.s et vous compilerez en tapant make somme pour utiliser le programme principal somme.c fourni. Testez bien l'exécution pas à pas du programme avec GDB : vous pouvez afficher le contenu d'une variable sur 8 bits en utilisant par exemple display (char)res.

uint8_t i, res;

uint8_t somme(void)
{
    res = 0;
    for (i = 1; i < 10; i++) {
        res = res + i;
    }
    return res;
}

Notez bien que dans ce programme, les variables globales i et res ne sont pas définies dans le programme principal : vous devez donc compléter la zone .data du programme assembleur pour les définir, en utilisant la directive .comm vu qu'elles ne sont pas initialisées.

Quand on traduit un programme du C vers l'assembleur, on indiquera toujours la ligne de C en commentaire avant la séquence d'instructions assembleur correspondante, par exemple :

    // res = 0;
    movb $0, res(%rip)

Multiplication simple

On va maintenant implanter l'opération res := x * y par additions successives. On donne ci-dessous le code C que l'on va devoir traduire le plus littéralement possible en assembleur, en complétant le fichier fct_mult.s.

uint64_t mult_simple(void)
{
    res = 0;
    while (y != 0) {
        res = res + x;
        y--;
    }
    return res;
}

On fournit un programme principal mult.c qui va tester toutes les versions de la multiplication avec d'abord les valeurs passées sur la ligne de commande (par exemple ./mult 10 5) puis avec 111111111 et 111111111, et finalement 2 et 2^{31}, et afficher le temps de calcul.

Les variables globales x et y sont déclarées dans mult.c, mais res doit être définie dans la zone .data du programme assembleur.

Multiplication egyptienne

Refaite le même exercice en implantant cette fois-ci l'algorithme de la multiplication égyptienne :

uint64_t mult_egypt(void)
{
    res = 0;
    while (y != 0) {
        if (y % 2 == 1) {
            res = res + x;
        }
        x = x * 2;
        y = y / 2;
    }
    return res;
}

Pour implanter les opérations modulo, multiplier et diviser par 2, vous aurez sûrement besoin des instructions suivantes :

  • test A, B compare A et B en effectuant l'opération A and B ;
  • shl $n, A décale A de n bits vers la gauche ;
  • shr $n, A décale A de n bits vers la droite (c'est un décalage logique, pas arithmétique).

Indication pour le test de la parité de y : l'instruction test effectue une conjonction logique (and) entre la constante 1 (qui s'écrit en binaire sur 64 bits "00..(60x 0 au milieu)..01") et y, ce qui peut donner 2 résultats :

  • soit 1 ssi le bit 0 de y vaut 1, c'est à dire ssi y est impair ;
  • soit 0 ssi le bit 0 de y vaut 0, c'est à dire ssi y est pair.

Si le résultat du test est 0, alors le flag Z passe à 1, et on peut utiliser l'instruction jz qui effectue le branchement ssi Z vaut 1 pour sauter le code dans le if ci-dessus.

Multiplication « native »

On va maintenant finir par implanter la multiplication en utilisant l'instruction de multiplication native du processeur, en traduisant le code ci-dessous :

uint64_t mult(void)
{
    res = x * y;
    return res;
}

Le processeur fournit une instruction de multiplication dont la syntaxe est un peu particulière. Si on suppose qu'on ne travaille ici que sur des valeurs sur 64 bits, lorsqu'on écrit mulq x(%rip), on effectue le produit de la valeur de la variable x avec le contenu du registre %rax : ce registre est donc un paramètre implicite de l'instruction.

Le résultat (sur 128 bits vu qu'on multiplie deux nombres sur 64 bits), est toujours stocké dans %rdx:%rax, c'est à dire que les 64 bits de poids fort du résultat sont dans %rdx, et les 64 bits de poids faibles dans %rax (par exemple si le résultat de la multiplication tient sur 64 bits, mul va écrire le résultat dans %rax et 0 dans %rdx. Si vous aviez mis quelque chose d'important dans %rdx, la donnée est perdue !).

Vous pouvez consulter la documentation de l'instruction si vous souhaitez en savoir plus.

Là encore, vous devez utiliser GDB pour vérifier que votre programme fonctionne. Vous n'avez pas besoin de vérifier que la multiplication ne déborde pas des 64 bits de %rax.