TD 2 - Assembleur X86-64

Si besoin, on pourra utiliser Nemiver (installé en salles info) pour exécuter pas à pas le code assembleur, ou encore gdb.

Cette page d'Andrew Tolmach donne pas mal de pointeurs pour écrire / débugger du code assembleur X86-64 et en particulier ces notes sur l'assembleur X86-64.

1. Petits exercices d'assembleur X86-64

On rappelle qu'un programme assembleur s'écrit dans un fichier portant le suffixe .s et ayant la forme suivante : 
      .text
      .globl main
main:
      ...
      mov  $0, %rax       # code de sortie
      ret
      .data
      ...
Vous pouvez compiler et exécuter ce fichier de manière non interactive avec la commande suivante : 
  gcc fichier.s && ./a.out

a. Expressions arithmétiques

Écrire des programmes en assembleur pour évaluer et afficher les résultats des expressions arithmétiques suivantes : Le résultat attendu est 
10
42
7
-9
Pour afficher un entier, on pourra se servir de la fonction suivante : 
print_int:
        mov     %rdi, %rsi
        mov     $message, %rdi  # arguments pour printf
        mov     $0, %rax
        call    printf
        ret
        .data
message:.string "%d\n"
solution avec des registres
solution avec la pile

b. Expressions Booléennes

En prenant pour convention que l'entier 0 représente la valeur Booléenne faux et que tout autre entier représente la valeur vrai, écrire des programmes en assembleur qui évalue et affiche les résultats des expressions suivantes (vous devez afficher true ou false dans le cas d'un résultat Booléen) : Le résultat attendu est 
false
20
true
Il pourra être utile d'écrire une fonction print_bool pour afficher un Booléen.
solution

c. Variables globales

Écrire un programme en assembleur qui évalue les trois instructions suivantes : 
  let x = 2
  let y = x * x
  print (y + x)
On allouera les variables x et y dans le segment de données. Le résultat attendu est 6.
solution

d. Variables locales

Écrire un programme en assembleur qui évalue le programme suivant : 
  print (let x = 3 in x * x)
  print (let x = 3 in (let y = x + x in x * y) + (let z = x + 3 in z / z))
On allouera les variables x, y et z sur la pile. Le résultat attendu est 
9
19
solution

2. Compilation d'un mini-langage

Le but de cet exercice est de réaliser un compilateur pour un mini-langage d'expressions arithmétiques, appelé Arith dans ce qui suit, vers l'assembleur X86-64. Un programme du langage Arith est composé d'une suite d'instructions, qui sont soit l'introduction d'une variable globale avec la syntaxe 
  set <ident> = <expr>
soit l'affichage de la valeur d'une expression avec la syntaxe 
  print <expr>
Ici, <ident> désigne un nom de variable et <expr> une expression arithmétique. Les expressions arithmétiques peuvent être construites à partir de constantes entières, de variables, de l'addition, de la soustraction, de la multiplication, de la division, de la négation, de parenthèses et d'une construction let in introduisant une variable locale. Plus formellement, la syntaxe des expressions arithmétiques est donc la suivante : 
  <expr> ::= <constante entière>
           | <ident>
           | ( <expr> )
           | <expr> + <expr>
           | <expr> - <expr>
           | <expr> * <expr>
           | <expr> / <expr>
           | - <expr>
           | let <ident> = <expr> in <expr>
Voici un exemple de programme dans le langage Arith : 
set x = 1 + 2 + 3*4
print (let y = 10 in x + y)
Les noms de variables sont formés de lettres et de chiffres et ne peuvent commencer par un chiffre. Les mots set, print, let et in sont réservés, i.e. ils ne peuvent être utilisés comme noms de variables. La priorité des opérateurs est usuelle et la construction let in a la priorité la plus faible.

Afin de vous aider à construire ce compilateur, nous vous fournissons sa structure de base (sous la forme d'un ensemble de fichiers Caml et d'un Makefile) que vous pouvez récupérer ici : arithc.tar.gz. Une fois cette archive décompressée avec tar zxvf arithc.tar.gz, vous obtenez un répertoire arithc/ contenant les fichiers suivants :

ast.mli la syntaxe abstraite d'Arith (complet)
lexer.mll l'analyseur lexical (complet)
parser.mly l'analyseur syntaxique (complet)
x86_64.mli, x86_64.ml pour écrire du code X86-64 (complet)
compile.ml la compilation proprement dite (à compléter)
main.ml le programme principal (complet)
Makefile pour automatiser la compilation (complet)

Le code fourni compile ; pour le compiler, faire make dans un terminal, ou mieux compiler depuis Emacs avec M-x compile ou encore C-c C-c ou encore F9 avec la configuration de l'ENS. Le code fourni est incomplet : le code assembleur produit est vide. Vous devez compléter le fichier compile.ml. Lorsque la compilation échoue, vous pouvez vous placer automatiquement sur l'erreur avec la commande M-x next-error ou encore Ctrl-x `. (Si ce raccourci ne vous plaît pas, changez-le comme expliqué au début du TD 1.)

L'exécutable s'appelle arithc et s'applique à un fichier Arith portant le suffix .exp, ainsi 

  ./arithc fichier.exp
ce qui a pour effet de produire un fichier fichier.s contenant le code assembleur. Vous pouvez alors exécuter ce fichier de manière non interactive avec la commande suivante 
  gcc fichier.s && ./a.out
Pour debugger, on pourra utiliser par exemple Nemiver, avec la commande nemiver a.out, puis le mode pas-à-pas avec F7.

Schéma de compilation

On réalisera une compilation simple utilisant la pile pour stocker les valeurs intermédiaires (i.e. les valeurs des sous-expressions). On rappelle qu'une valeur entière occupe 8 octets en mémoire. On peut allouer 8 octets sur la pile en soustrayant 8 à la valeur de %rsp ou encore en utilisant l'instruction pushq.

Les variables globales seront allouées dans le segment de données (directive .data de l'assembleur ; ici cela correspond au champ data du type X8_64.program).

Les variables locales seront allouées au fond de la pile. La place nécessaire pour l'ensemble des variables locales sera allouée au démarrage du programme (par une soustraction adéquate sur %rsp). Le registre %rbp sera positionné de manière à pointer sur le fond de la pile ; ainsi toute référence à une variable locale se fera par rapport à %rbp.

Travail à faire

Vous devez lire soigneusement le code qui se trouve dans compile.ml. Les parties à compléter, marquées (* À COMPLÉTER*), sont les suivantes :
  1. La fonction compile_expr qui compile une expression arithmétique e en une suite d'instructions X86-64 dont l'effet est de déposer la valeur de e au sommet de la pile. Cette fonction est définie en utilisant une fonction récursive locale comprec qui prend comme arguments :

  2. La fonction compile_instr qui compile une instruction de Arith en une suite d'instructions X86-64. Dans les deux cas (set x = e ou print e), on doit commencer par compiler e, puis on trouve la valeur de e en sommet de pile (ne pas oublier de dépiler).

  3. La fonction compile_program qui applique compile_instr à toutes les instructions du programme et ajoute du code :

Indications : on pourra procéder construction par construction, en testant à chaque fois, dans l'ordre suivant :

  1. expression constante Cst, instruction Print et sortie avec ret ;
  2. opérations arithmétiques (constructeur Binop) ;
  3. variables globales (constructeurs Var et Set) ;
  4. variables locales (constructeurs Letin et Var).

On testera au final avec le fichier test.exp (également fourni), dont le résultat doit être le suivant : 

60
50
0
10
55
60
20
43
solution

Question optionnelle

Pour utiliser un peu moins d'espace sur la pile, on peut améliorer un peu ce schéma de compilation pour que le résultat de compile_expr se retrouve dans le registre %rax plutôt qu'en sommet de pile. Ainsi, seuls les résultats de sous-expressions gauches se retrouvent empilés.
solution
retour à la page du cours