SE202 : déroulement du cours et bases de compilation

Samuel Tardieu

Année scolaire 2016/2017

Organisation du cours

Objectifs

À la fin de ce module, les étudiants :

Déroulement du cours

Le projet

Introduction à la compilation

Le fonctionnement d'un microprocesseur

Un microprocesseur :

Le fonctionnement d'un microprocesseur

Un microprocesseur ne sait pas faire

int c = a + 3 * b - 2

Ce qu'il sait faire ressemble plus à :

r0 <- MEM[a]
r1 <- MEM[b]
r2 <- r1 * 3
r3 <- r0 + r2
r4 <- r3 - 2
MEM[c] <- r4

Le fonctionnement d'un microprocesseur

Pour compliquer un peu la chose :

Les jeux d'instructions peuvent être très différents :

L'assembleur à la rescousse

Qu'est-ce que la compilation ?

Définition approximative

La compilation est la transformation d'un programme source écrit en langage de haut niveau en instructions compréhensibles par l'ordinateur.

Exemples

La machine virtuelle Java

Qu'est-ce que la compilation ?

Meilleure définition

La compilation est la transformation d'un programme dans un format d'entrée donné dans un programme dans un format de sortie donné.

Exemples

Compilation et interprétation

Quand on a par exemple un bytecode Java, destiné à la machine virtuelle, on peut :

Exemple : Android

On a donc du code portable, que le téléphone ait un microprocesseur ARM ou un microprocesseur Intel.

Autres types de compilation

Il est possible de compiler un langage de programmation vers un autre :

La compilation fait partie d'un tout

On utilise souvent le principe de compilation séparée :

Une phase d'édition de liens recolle ensuite les différents morceaux afin d'en faire un programme complet prêt à s'exécuter sur le système cible.

Le compilateur peut également générer des informations supplémentaires qui aideront au débogage.

La compilation n'est pas unique

Optimisation

L'optimisation consiste à :

Exemple d'optimisation (en C)

int f() {
  return 1 + 2 * 3;
}
% clang -S -O2 -o - t.c
f:
    movl    $7, %eax  ; eax <- 7
    retq              ; retour du résultat dans eax

Le compilateur a pu calculer la valeur de l'expression (assez facile). Qu'en est-il des expressions plus complexes avec des boucles ?

Exemple d'optimisation (en C)

int f(int a) {
  int r = 12;
  for (int i = 0; i < 100; i++)
    r += 3 * (a - 1) * i + 7;
  return r - 1;
}
% clang -S -O2 -o - t.c
f:
  imull $14850, %edi, %eax  ; eax = 14850 * a
  addl  $-14139, %eax       ; eax = 14850 * a - 14139
  retq                      ; retour du résultat dans eax

Comment a fait le compilateur ?

int f(int a) {
  int r = 12;
  for (int i = 0; i < 100; i++)
    r += 3 * (a - 1) * i + 7;
  return r - 1;
}

a été transformé en

int f(int a) {
  int r = 12;
  for (int i = 0; i < 100; i++)
    r += a * (3 * i) - (3 * i) + 7;
  return r - 1;
}

Comment a fait le compilateur ?

Puis

int f(int a) {
  int r = 12;
  for (int i = 0; i < 100; i++)
    r += a * (3 * i) - (3 * i) + 7;
  return r - 1;
}

a été transformé en ($\sum_{i=0}^{99}i = 4950$)

int f(int a) {
  int r = 12;
  r += a * 3 * 4950 - 3 * 4950 + 7 * 100;
  return r - 1;
}

Comment a fait le compilateur ?

Ensuite

int f(int a) {
  int r = 12;
  r += a * 3 * 4950 - 3 * 4950 + 7 * 100;
  return r - 1;
}

a été transformé en

int f(int a) {
  // return 12 + a * 3 * 4950 - 3 * 4950 + 7 * 100 - 1;
  return 14850 * a - 14139
}

Quand faire les optimisations ?

Les optimisations pourraient se faire sur le code d'origine, mais cela a peu d'intérêt (obligation de regénérer du code source valide).

Elles interviennent en général plus tard dans le processus de compilation.

Processus de compilation

Lien entre source et cible

Traduit on directement la source en IR ?

La représentation intermédiaire est agnostique du langage source. Elle ne permet pas de faire facilement des manipulations dépendantes du langage.

Pour cela, on rajoute une étape intermédiaire : l'AST (Abstract Syntax Tree, ou arbre syntaxique abstrait). Cet arbre, propre au langage source, est une représentation du programme en entrée. On pourrait par exemple reconstituer le programme en partant de l'AST.

Exemple d'AST

Le fragment de code C suivant

if (a > 3)
  b = 10;
else
  b = 20;

pourra par exemple correspondre à l'arbre

If(Binop(">", Identifier(a), Number(3)),
   Assign(Identifier(b), Number(10)),
   Assign(Identifier(b), Number(20)))

La racine est un nœud IF avec trois champs, correspondant respectivement à la condition, la partie à exécuter si la condition est vérifiée et celle à exécuter si elle ne l'est pas.

Exemple d'AST

Autre exemple :

int f(int a) {
 a = a + 1;
 return a * 3;
}

peut correspondre à

Fundecl(f, Type(int), [Param(a, Type(int))],
        [Assign(Identifier(a),
           Binop("+", Identifier(a), Number(1))),
         Return(Binop("*", Identifier(a), Number(3)))
        ]
       )

Construction de l'AST

L'AST est généralement construit à partir du programme source à partir de deux outils :

Lexer

Par exemple, le code C suivant

int f(int a) {
  return a + 1;
}

donné au lexer produira la suite de tokens suivants :

IDENTIFIER("int"), IDENTIFIER("f"), LPAREN,
IDENTIFIER("int"), IDENTIFIER("a"), RPAREN,
LBRACKET, KEYWORD("return"),
IDENTIFIER("a"), PLUS, NUMBER(1), SEMICOLON,
RBRACKET

Lexer

Le lexer ne comprend vraiment rien au langage lui-même. Par exemple, si on lui demande d'analyser la ligne

int a = b(3};

il renverra sans broncher

IDENTIFIER("int"), IDENTIFIER("a"), EQUAL,
IDENTIFIER("b"), LPAREN, NUMBER(3), RBRACKET,
SEMICOLON

sans s'apercevoir qu'une accolade (RBRACKET) ferme la parenthèse (LPAREN). Son rôle n'est pas de s'assurer que le programme est syntaxiquement correct (ou qu'il suit la grammaire du langage) : c'est au parser de faire cela.

Parser

Le parser est créé à partir d'un ensemble de règles ressemblant à

assignment : IDENTIFIER EQUAL expression SEMICOLON
expression : expression PLUS expression
           | NUMBER
           | IDENTIFIER
           | LPAREN expression RPAREN

Cela signifie que :

Actions

À chaque règle du parser on peut associer une action permettant de construire l'AST :

assignment : IDENTIFIER EQUAL expression SEMICOLON
  => Assignment(Identifier($1), $3)

expression : expression PLUS expression
               => Binop("+", $1, $3)
           | NUMBER                     => Number($1)
           | IDENTIFIER                 => Identifier($1)
           | LPAREN expression RPAREN   => $2

Ici, Expression est un type abstrait qui a comme descendant Binop, Identifier et Number. Et Assignment a deux champs, un Identifier et une Expression.

Priorité et associativité

Il est possible d'associer une priorité (precedence) ainsi qu'une associativité aux opérateurs :

Actions

Après l'exécution du parseur, on se retrouve avec un AST construit récursivement :

Analyse sémantique

La phase d'analyse sémantique essaie de donner du sens à l'AST :

Ainsi, à la fin de l'analyse sémantique, chaque identifiant fera référence à sa déclaration. Lorsqu'on parlera de a, on saura de quel a on parle même s'il y en a plusieurs à différents endroits du programme.

Analyse sémantique

Voici le type de lien qu'on trouve après l'analyse sémantique par exemple :

int a; <--------------+
int b; <---------+    |
                 |    |
int f() { return b; } |
                      |
int g(int b) { return a + b; }
          ^               |
          |               |
          +---------------+

Ces liens seront primordiaux pour savoir quelle registre ou adresse mémoire lire ou modifier lorsqu'on générera le code final.

Analyse sémantique

Lors de l'analyse sémantique, on regarde d'autres choses que les variables :

Ambiguïté

Certains langages comme le C sont ambigus et l'arbre peut nécessité d'être modifié lors de l'analyse. Que signifie b * a en C ?

int a;
int b;
typedef int c;

void f() {
  b * a;
  c * a;
}

Ça dépend : il est nécessaire de savoir, pour analyser * a, de savoir si ce qui précède est un type (déclaration de variable locale de type pointeur sur b) ou une variable (multiplication par c).

Récapitulatif

C'est ce que vous aurez à faire pour le langage Tiger au tout début de votre projet.

Les étapes suivantes

Une fois l'AST décoré, il restera à (au fur et à mesure du projet) :

Mais en attendant

Il est temps de parler du projet.