TD 1 - Assembleur x86-64

Si besoin, on pourra utiliser gdb pour exécuter pas à pas le code assembleur.

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 -g -no-pie 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 pour évaluer et afficher 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) 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.ml 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)
arithc.ml le programme principal (complet)
Makefile/dune pour automatiser la compilation (complet)

Le code fourni compile (taper make, qui va lancer dune build) mais il est incomplet : le code assembleur produit est vide. Vous devez compléter le fichier compile.ml.

Le programme attend un fichier Arith portant le suffix .exp. Quand on fait make, le programme est lancé sur le fichier test.exp, ce qui a pour effet de produire un fichier test.s contenant le code assembleur, puis les commandes 

  gcc -g -no-pie test.s -o test.out
  ./test.out
sont lancées. Pour debugger, on pourra examiner le contenu de test.s et si besoin utiliser un debugger comme gdb avec la commande gdb ./test.out puis le mode pas-à-pas avec step).

Note aux utilisateurs de macOS : il faut modifier la ligne let mangle = mangle_none dans le fichier x86_64.ml fourni, pour la remplacer par let mangle = mangle_leading_underscore. Il faut également remplacer let lab = abslab par let lab = rellab.

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 sur 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), après la sauvegarde de %rbp. Le registre %rbp sera positionné de manière à pointer sur le haut de l'espace réservé aux variables locales, comme ceci : 

          +-------------+
          | adr. retour |
          +-------------+
          | ancien %rbp |
  %rbp -> +-------------+  ^
          | var. locale |  |
          | var. locale |  |  frame_size (multiple de 16)
          | ...         |  |
  %rsp -> +-------------+  v
Ainsi, toute référence à une variable locale se fera par rapport à %rbp, avec un décalage -8, -16, etc., selon la variable.

Attention : avant d'appeler une fonction de bibliothèque comme printf, la pile doit être alignée sur 16 octets. Une fois la valeur de frame_size déterminée, on assure donc que c'est un multiple de 16 (voir le code fourni).

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