Rappels de cours

L'objectif de cette partie du cours est de comprendre le rôle que joue un compilateur. Un compilateur prend en entrée un programme dans un langage de haut niveau, par exemple Java, et le transforme en un programme dans un langage de bas niveau, typiquement de l'assembleur, qui a le même comportement que le programme de haut niveau.

L'aspect de cette transformation qui nous intéresse dans cette partie est la manière dont le flot de contrôle du programme est traduit. Concrètement, les programmes Java contiennent des conditionnelles if-else et des boucles for et while, alors que l'assembleur utilise d'autres constructions pour contrôler le flot de contrôler les sauts non conditionnels et les sauts conditionnels.

Forme générale d'un programme assembleur

Un programme en assembleur est composé d'une liste d'instructions, et chaque instruction possède une adresse. Dans ce document, on suppose que son adresse est son numéro de ligne.

Au lieu de variables comme en Java, l'assembleur utilise des registres, qui contiennent chacun un entier (en gros, ce sont des variables de type int). Chaque architecture de processeur comporte un certain nombre de registres. Par exemple, ARMv8 contient 31 registres X0,...,X30 pouvant chacun contenir 64 bits.

Un exemple de programme est :

ldr X4, X6   // copie le contenu de X6 dans X4 (load register)
b 1          // saute (branch) de 2 lignes
cmp X4, X7   // compare les contenus de X4 et de X7
b.eq -4      // saute de -3 instructions si la dernière comparaison était égale

L'adresse de la prochaine instruction à exécuter est contenue dans un registre spécial, le compteur d'instructions, ou ic.

Dans ce cours, on simule un tel programme assembleur en un programme Java ayant un forme très particulière. Pour cet exemple, il ressemblerait à :

int ic=0;

while (true) {
    switch (ic++) {
        case 0: mem[4]=mem[6]; break;
        case 1: ic+=1; break;
        case 2: if (mem[4] == mem[7]) ic-=3; break;
    }
}

Notez que les deux dernières instructions du programme assembleur (test + saut) correspondent à une seule ligne dans la version en Java.

Sauts non-conditionnels

Quand on exécute un saut conditionnel b offset, la prochaine instruction à être exécutée est l'instruction à l'adresse courante à laquelle on a ajouté offset. Ce qui correspond dans la version Java à ic += offset.

Sauts conditionnels

En assembleur, les sauts conditionnels se font de deux étapes:

  1. Une instruction de comparaison, par exemple cmp qui enregistre le résultat dans un registre spécial.
  2. Une instruction de saut conditionnelle qui saute si ce registre a une certaine valeur. Par exemple b.eq pour sauter si la dernière comparaison était entre des opérandes qui étaient égales, ou b.gt qui saute si le résultat de la dernière comparaison était "plus grand que".

Dans la version java, on combine ces deux instructions en une seule ligne:

case X: if (condition) ic += offset' break'

Remarque : pour ceux que ça amuse, le site godbolt.org est très bien pour explorer comment les compilateurs traduisent les programmes.

Structure générale des programmes traduits

L'idée est de traduire un programme tel que celui-ci :

class Prog {
    public static void main(String[] a) {
        int k = 0;
        for (int i = 0; i < 6; i++) {
            k += i;
        }
    }
}

en un programme de la forme

class ProgTrad {
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: mem[0]=0; break;
                case 1: mem[1]=0; break;
                case 2: if (mem[0]>=6) ic+=3; break;
                case 3: mem[1]+=mem[0]; break;
                case 4: mem[0]++; break;
                case 5: ic-=4; break;
                case 6: System.exit(0);
            }
        }
    }
}

Post-incrémentation

Il est important de bien comprendre la ligne

switch (ic++) {

et en particulier le fonctionnement de la post-incrémentation ic++, qui est assez surprenant: qu'affiche le programme suivant?

int x = 4;
if (x++ == 4) {
    System.out.println("Branche gauche, et x vaut" + x);
} else {
    System.out.println("Branche droite, et x vaut" + x);
}

La réponse est Branche gauche, et x vaut 5. La raison est la suivante : la valeur de l'expression x++ est l'ancienne valeur de x, mais le fait d'évaluer cette expression ajoute 1 à x.

Moralement, c'est comme si tous les x++ étaient remplacés par incr(x), un appel à la fonction Java suivante :

public static int incr(int i) {
    int old = i;
    i = i + 1;
    return old
}

sauf qu'en Java les entiers sont passés par valeur, et donc cette fonction ne modifie pas la valeur de x (s'en convaincre).

Pour revenir à nos traductions, cela signifie que si un branche case X ne modifie pas ic, la valeur de ic devient X+1. En somme, l'exemple en haut est équivalent à :

class ProgTrad {
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic) {
                case 0: ic += 1; mem[0]=0; break;
                case 1: ic += 1; mem[1]=0; break;
                case 2: ic += 1; if (mem[0]>=6) ic+=3; break;
                case 3: ic += 1; mem[1]+=mem[0]; break;
                case 4: ic += 1; mem[0]++; break;
                case 5: ic += 1; ic-=4; break;
                case 6: ic += 1; System.exit(0);
            }
        }
    }
}

Après que le choix de quelle branche choisir est fait, et avant tout autre chose, on ajoute 1 à ic.

Comment traduire un programme Java

Puisque le but de ce cours est de mieux comprendre ce que fait un compilateur, il nous faut être méthodique. En particulier, on veut que la traduction soit modulaire : chaque construction du programme est traduite sans se soucier du reste du programme. Par exemple, considérons le programme suivant :

class Prog{
    static int i;
    static int k;
    public static void main(String[] a){
        int cpt = 0;
        int k = 10;
        while(k != 1){
            if (k % 2 == 0) { 
                k = k/2;
            } else {
                else k = 3*k+1;
            }
            cpt++;
        }
    }
}

Dans cet exemple, les constructions principales sont : la boucle while et la conditionnelle if. Commençons par la boucle while.

Traduire les boucles while

Une boucle while a cette forme :

while (condition) {
    corps de la boucle;
}

Le flot d'exécution est :

  1. On exécute la condition, ce qui nous donne un booléen.
    • Si ce booléen est vrai, on exécute l'instruction suivante.
    • S'il est faux, on saute la boucle.
  2. On exécute le corps de la boucle.
  3. On recommence à l'étape 1.

On reconnais que l'étape 3 est un saut non conditionnel vers l'instruction qui correspond à 1 ; et l'étape 1 est un saut conditionnel si la condition est fausse. Ainsi la traduction est la suivante:

case X: if (!condition) ic += (Y-X); break;
case X+1: [[ traduction du corps de la boucle ]]
case X+2: [[ ................................ ]]
case X+3: [[ ................................ ]]
case ...: [[ ................................ ]]
case Y: ic -= (Y-X)+1; break;
case Y+1: [[ traduction de la suite du programme ]]

Exercice : comment traduire une boucle do {...} while (cond); ? (C'est comme un boucle while sauf que le corps de la boucle est exécuté au moins une fois)

Traduire une boucle for

Ce cas est similaire au cas des boucles while, avec quelques ajouts. Une boucle for est de la forme :

for (initialisation; condition; incrément) {
    corps de la boucle;
}

Souvent les boucles for sont utilisées pour itérer de 0 jusqu'à N-1:

for (int i = 0; i < N; i++) {
    corps de la boucle;
}

De la même manière que pour les boucles while, on écrit le flot d'exécution d'une boucle for:

  1. On exécute initialisation.
  2. On exécute la condition, ce qui nous donne un booléen.
    • Si ce booléen est vrai, on exécute l'instruction suivante.
    • S'il est faux, on saute la boucle.
  3. On exécute le corps de la boucle.
  4. On exécute incrément.
  5. On recommence à l'étape 2.

Il s'agit du même flot que pour une boucle while en ajoutant une étape d'initialisation au début et une étape d'incrémentation à la fin de la boucle. La traduction est donc de la forme :

case X  : intialisation
case X+1: if (!condition) ic += (Y-X)+1; break; // saute vers Y+2
case X+2: [[ traduction du corps de la boucle ]]
case X+3: [[ ................................ ]]
case X+4: [[ ................................ ]]
case ...: [[ ................................ ]]
case Y  : incrémentation
case Y+1: ic -= (Y-X)+1; break;
case Y+2: [[ traduction de la suite du programme ]]

Traduire une conditionnelle

On considère une conditionnelle

if (condition) {
    branche_then;
} else {
    branche_else;
}

Le flot de considère est le suivant:

  1. On exécute la condition.
    • Si elle est vraie:
      • on exécute branche_then,
      • on saute vers la première instruction après la conditionnelle.
    • Si elle est fausse:
      • on saute vers branche_else,

Ainsi, on ne fait un saut conditionnel que lorsque la condition est fausse. La traduction est donc:

case X: if (!cond) ic += ...; // on saute vers Y+1
case X+1: [[ traduction de branche_then ]]
case X+2: [[ .......................... ]]
case X+3: [[ .......................... ]]
case X+4: [[ .......................... ]]
case ...: [[ .......................... ]]
case Y: ic +=  ...; // on saute vers Z
case Y+1: [[ traduction de branche_else ]]
case Y+2: [[ .......................... ]]
case Y+3: [[ .......................... ]]
case Y+4: [[ .......................... ]]
case ...: [[ .......................... ]]
case Z : [[ traduction de la suite du programme ]]

Concrètement, si la condition est vraie, on ne saute pas, donc on exécute X+1, ensuite le code de la branche fait ce qu'elle veut, et quand elle a terminée on exécute Y qui nous fait sauter au dessus de la branche else jusqu'à la suite du code.

Si la condition est fausse, on commence par sauter au dessus de la branche then et on commence à exécuter la branche else, puis la suite du programme.

Exercice : Comment traduire if (cond1) {...} else if (cond2) {...} else {...} ?

Gestion de la mémoire

Dans la traduction, on ne veut utiliser qu'un unique tableau d'entiers, qu'on va appeler ici mem.

Chaque variable statique sera associée à une certaine case de ce tableau. La difficulté apparait quand une variable statique est elle-même un tableau d'entiers.

Imaginons que nous devons traduire un programme avec les variables statiques suivantes :

static int x;
static int y;
static int[] t1 = new int[58];
static int[] t2 = new int[30];

(On connaitra toujours la taille de ces tableaux à l'avance.) Il s'agit donc de ranger toutes ces variables dans le tableau mem. Une possibilité est:

0   1   2                 60            90
+---+---+-----------------+-------------+
| x | y |    ...t1...     |  ...t2...   |
+---+---+-----------------+-------------+

Ainsi, la valeur de x est dans mem[0], et a valeur de la j-ème case de t2 est dans mem[60 + j], puisque le tableau t1 commence à la case 60 de mem.

Pour traduire t2[x], on utilisera alors mem[60 + mem[0]]. Notez que la valeur de x dans le programme d'origine reste la même que la valeur de mem[0] dans le programme traduit.