INF564 - TD 1 - Assembleur x86-64

L'objectif de ce TD est de se familiariser avec l'assembleur x86-64 en compilant à la main de petits programmes C.

On rappelle qu'un programme assembleur s'écrit dans un fichier portant le suffixe .s et a 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 fichier.s -o fichier
  ./fichier

(Ajouter l'option -no-pie si vous utilisez une version de gcc supérieure ou égale à 5.)

Si besoin, on pourra utiliser gdb (installé en salles info) pour exécuter pas à pas le code assembleur. Pour cela, faire

gdb ./fichier
(gdb) break main
(gdb) run

puis exécuter pas à pas avec la commande step. Plus d'information sur gdb dans ce tutoriel.

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.

Affichage avec printf

Compiler le programme suivant :

#include <stdio.h>

int main() {
  printf("n = %d\n", 42);
  return 0;
}

Pour appeler la fonction de bibliothèque printf, on passe son premier argument (la chaîne de format) dans le registre %rdi et son second argument (ici l'entier 42) dans le registre %rsi, comme le veulent les conventions d'appel. On doit aussi mettre le registre %rax à zéro avant d'appeler printf, car il s'agit d'une fonction variadique (i.e. avec un nombre d'arguments variable) et %rax indique le nombre de paramètres passés dans des registres vecteurs (ici aucun).

La chaîne de format doit être déclarée dans le segment de donnée (zone .data) avec la directive .string qui ajoute le caractère de code 0 à la fin de la chaîne.

solution

Racine carrée entière

Compiler le programme suivant :

#include <stdio.h>

int isqrt(int n) {
  int c = 0, s = 1;
  while (s <= n) {
    c++;
    s += 2*c + 1;
  }
  return c;
}

int main() {
  int n;
  for (n = 0; n <= 20; n++)
    printf("sqrt(%2d) = %2d\n", n, isqrt(n));
  return 0;
}

On essayera notamment d'effectuer les optimisations suivantes :

une seule instruction de branchement par tour de boucle ;
une seule instruction assembleur pour compiler l'instruction s += 2*c + 1.

solution

Un programme un peu plus complexe (et un peu plus intéressant)

On va maintenant compiler un programme C qui résout le problème suivant : étant donnée cette matrice d'entiers de dimension 15x15, déterminer la somme maximale que l'on peut obtenir en utilisant uniquement un élément par ligne et un élément par colonne. (Il s'agit du problème 345 du projet Euler.)

Le programme C matrix.c contient une solution, qu'on lira attentivement. Cette solution utilise les deux ingrédients suivants :

On généralise le problème pour un certain sous-ensemble de lignes et de colonnes. Ce sous-ensemble est défini par deux entiers i et c :
- On ne considère que les lignes i..14 ;
- On ne considère que les colonnes j pour lesquelles le bit j de l'entier c vaut 1. (Il est toujours assuré que c a exactement 15-i bits valant 1.)
L'appel f(i, c) calcule la somme maximale pour le sous-ensemble de la matrice défini par i et c.
On utilise le principe de mémoïsation, pour ne pas calculer plusieurs fois f(i, c). Pour cela, un tableau memo est déclaré. On y stocke le résultat de f(i, c) à l'indice c << 4 | i, s'il est déjà calculé, et 0 sinon.

Représentation de la matrice

En C, la matrice m est déclarée sous la forme

const int m[N][N] = { { 7, 53, ..., 583 }, { 627, 343, ... }, ... };

En mémoire, les entiers sont stockés consécutivement, ligne par ligne. Chaque entier occupe 4 octets et la matrice m occupe donc 900 octets au total. L'entier m[i][j] se trouve en mémoire à l'adresse m + 4 * (15*i + j).

On fournit un fichier matrix.s contenant déjà la déclaration statique de la matrice m, ainsi que la place pour le tableau memo. Comme ce dernier est initialisé avec zéro, il est alloué dans la section .bss pour ne pas occuper inutilement de la place dans l'exécutable.

Compilation du programme

Compiler les fonctions f et main. En ce qui concerne la fonction f, il faut notamment allouer des registres pour ses variables locales key, r, s, etc. Si on utilise un ou plusieurs registres callee-saved, il faudra les restaurer. Si on utilise un ou plusieurs registres caller-saved, il faudra les restaurer après un appel si les registres concernés sont utilisés après l'appel.

Attention : pour calculer 1 << j, il faut effectuer un décalage d'une valeur non constante. Pour cela, l'opérande de l'instruction sal, c'est-à-dire la valeur de j ici, doit être placée dans le registre octet %cl. Il pourra donc être intéressant d'allouer la variable j dans le registre %rcx.

solution

retour à la page du cours