Projet de compilation (Étape 4)

SE202 - Année scolaire 2015/2016

Quatrième étape

Avant de commencer

Avant de commencer à travailler, il vous faut intégrer le code venant de l'équipe pédagogique. Depuis votre dépôt :

% git pull template step4

À ce stade, votre dépôt a été enrichi de l'étape step4 du dépôt de référence. Vérifiez que les tests de base fonctionnent toujours :

% workon tiger
(tiger)% python -m unittest

La première commande fait appel à votre environnement de développement virtuel tiger, si ce n'était pas déjà fait. La seconde cherche tous les tests unitaires du dépôt et les exécute.

Travail à faire

La traduction vers la représentation intermédiaire (IR) est fournie par l'équipe pédagogique. Durant cette étape, vous aurez à découper les instructions en blocs basiques et à les réordonner.

La représentation intermédiaire utilise un nouveau type d'arbre localisé dans ir/nodes.py. Certains nœuds vont être détaillés par la suite.

Fonctions intrinsèques

Une fonction intrinsèque est une fonction dont le code est fourni par le système d'exploitation ou la bibliothèque de support de compilateur.

Le programme tiger.py et le squelette du binder ont été enrichis pour fournir deux fonctions intrinsèques :

  • print_int(n: int) affiche un entier sur la sortie standard (sans retour chariot) ;
  • exit(n: int) sort du programme avec un code d'erreur (ou 0 si tout va bien).

De plus, la valeur renvoyée par votre programme principal est implicitement incluse dans une fonction main.

Objets supports de l'IR

Deux objets supports sont utilisés dans le cadre de l'IR :

  • Label représente un nom logique utilisé plus tard dans le cadre de la génération du langage assembleur ;
  • Temp représente un registre nommé soit à partir d'un registre physique soit à partir d'un registre virtuel avec un suffixe explicatif optionnel.

Ces deux classes disposent d'une méthode create permettant de créer un nouvel objet.

Les types de nœuds

Les nœuds de l'arbre intermédiaire sont divisés en deux catégories :

  • les nœuds enfants de Sxp représentent une expression renvoyant un résultat (Simple eXPression, une opération binaire par exemple);
  • les nœuds enfants de Stm représentent un StaTeMent, qui ne renvoie pas de résultat (un transfert de registres par exemple).

Tous les nœuds sont documentés dans ir/nodes.py. Leurs noms sont écrits entièrement en majuscules pour les distinguer de deux de l'arbre syntaxique présent dans ast/nodes.py.

Les nœuds de l'IR

  • BINOP (Sxp) représente une opération binaire entre deux Sxp.
  • CALL (Sxp) représente un appel de fonction (qui renvoie un résultat).
  • JUMP (Stm) représente un saut inconditionnel. Il prend un Sxp comme paramètre, car on peut sauter à une adresse calculée par une formule ou une fonction. Si on veut sauter à un label de type Label, on l'encapsulera dans un nœud NAME qui est de type Sxp.

Les nœuds de l'IR

  • CJUMP (Stm) est un saut conditionnel en fonction du résultat d'un opérateur logique binaire. Il prend en paramètres l'opérateur (une chaîne de caractères), les deux opérandes (des Sxp) et les deux labels (des Sxp) correspondant à l'endroit où sauter si le test est vrai et si le test est faux respectivement.
  • CONST (Sxp) représente une constante entière.
  • SXP (Stm) permet d'indiquer qu'on ne souhaite pas utiliser la valeur de l'expression (Sxp) passée en paramètre.

Les nœuds de l'IR

  • LABEL (Stm) est une déclaration de label (qui prend en paramètre un objet de type Label).
  • NAME (Sxp) prend également un objet de type Label en paramètre et sert à le désigner comme cible d'un saut par exemple : JUMP(NAME(Label("main"))).
  • TEMP (Sxp) est un registre (virtuel ou physique) qui prend en paramètre un objet de type Temp).
  • MOVE (Stm) est un transfert vers une destination (Sxp) d'une source (Sxp). Par exemple, pour transférer le résultat de l'opération 3*4 dans le registre physique r3, on utilisera : MOVE(TEMP(Temp("r3")), BINOP("*", CONST(3), CONST(4))).

Les nœuds de l'IR

  • SEQ (Stm) prend en paramètres une liste de statements (de type Stm) et les exécute à la suite.
  • ESEQ (Sxp) prend en paramètres un Stm a exécuter en premier, puis un Sxp représentant l'expression à évaluer. Par exemple, pour mettre le résultat de 1+2 dans le registre virtual t_4 et utiliser sa valeur, on utilisera : ESEQ(MOVE(TEMP(Temp("t_4")), BINOP("+", CONST(1), CONST(2))), TEMP(Temp("t_4"))).

Visualisation de l'IR

Le programme tiger.py permet, avec le paramètre -i, de visualiser la sortie en langage intermédiaire, en utilisant les registres ARM ou les registres de la machine virtuelle IRVM si -I est également donné :

% ./tiger.py -iIdE "42"
seq
  label main
  move
    temp rv
    const 42
  label end
seq end

Visualisation de l'IR

On remarquera plusieurs choses :

  • La machine virtuelle IRVM utilise le registre rv pour placer la valeur de retour.
  • Les SEQ sont affichées entre seq et seq end.
  • Un label end indique la fin d'une fonction (équivalent à un return).

Le code du dumper pour l'IR est disponible dans ir/dumper.py.

Visualisation de l'IR au format Arm

Si on omet le -I, les conventions d'appel sont celles de l'ABI ARM, avec une valeur de retour dans r0 :

% ./tiger.py -idE "42" 
seq
  label main
  move
    temp r0
    const 42
  label main$$end
seq end

Forme canonique

L'arbre n'est pas sous forme canonique prêt à être transformé en assembleur. Par exemple, les appels de fonction (nœuds CALL) peuvent prendre d'autres appels de fonction en paramètre. Vous pouvez le visualiser en utilisant par exemple :

% ./tiger.py -iIdE "let function f(n: int) = n \
  in f(f(3)) end"

Bien entendu, un appel de fonction utilisant les registres, il faudrait plutôt sérialiser les appels. C'est le rôle de la mise sous forme canonique, que l'on peut trouver dans les fichiers ir/canonical.py et ir/hoist.py.

Forme canonique

On peut effectuer la transformation sous forme canonique en ajoutant -c à la ligne de commande (rappel : --help ou -h permet d'obtenir l'aide) :

% ./tiger.py -ciIdE "let function f(n: int) = n \
  in f(f(3)) end" 

On remarquera que le résultat de f(3) est stocké dans un registre intermédiaire avant de procéder au second appel à f. De plus, on ne trouve plus de nœuds ESEQ, et il n'y a plus qu'un seul nœud SEQ par fonction qui représente le code de cette fonction.

Exécution avec IRVM

Le programme irvm écrit par Pablo Oliveira permet d'éxécuter le code IR :

% ./tiger.py -ciIdE "let function f(n: int) = n*2 \
  in print_int(f(f(3))) end" > /tmp/t.ir 
% irvm /tmp/t.ir     
12

Installation et compilation d'IRVM

% cd /tmp
% git clone https://github.com/pablooliveira/irvm
% cd irvm
% ./autogen.sh
% ./configure
% make
% export PATH=$PWD/src:$PATH

ou

% sudo make install

sur votre propre machine (à la place de la dernière commande). Il est possible de devoir installer les paquets autoconf, texinfo, flex et bison si vous ne les avez pas en local.

À faire

Il vous faudra vérifier que votre arbre est bien construit en écrivant de petits programmes en Tiger qui devront afficher le bon résultat. Ces programmes devront contenir, sur la première ligne, en commentaire //, le résultat attendu, et se trouver dans des fichiers .tiger du répertoire tests :

  • un calcul récursif de factorielle ;
  • un calcul non-récursif de factorielle (avec accumulateur) ;
  • un calcul de la fonction de Fibonacci (calculez fibo(15) par exemple) ;
  • des exemples utilisant les boucles ;
  • des exemples utilisant les fonctions imbriquées ;
  • des exemples utilisant break.

Exemple de programme Tiger

Dans le fichier tests/facta.tiger, vous pourrez par exemple avoir le calcul de factorielle avec accumulateur :

// 3628800
let
  function facta(n: int, a: int) =
    if n < 2 then a else facta(n-1, a*n)
  function fact(n: int) = facta(n, 1)
in
  print_int(fact(10))
end

Notation

Une note sera attribuée à la qualité des programmes Tiger écrits et à leur résultat. N'hésitez pas à utiliser également d'autres fonctionnalités du langage. Vous n'êtes pas autorisés à reprendre les programmes de quelqu'un d'autre.

Un petit bonus pourra être accordé à ceux qui trouveront des bugs dans la traduction en langage intermédiaire, et un bonus plus important à ceux qui proposeront des corrections.

Attention à bien comprendre la représentation intermédiaire : c'est au programme du contrôle de la semaine prochaine.

Travail supplémentaire

Pour ceux qui souhaitent un bonus, un travail supplémentaire est proposé qui touche à toutes les étapes vues jusqu'à présent :

  • ajouter un mot clé return qui permet de retourner de manière anticipée d'une fonction (avec ou sans valeur) ;
  • afficher return correctement ;
  • lier return à la fonction englobante ;
  • typer le nœud return (qui lui-même est de type void) ;
  • transformer le nœud return en IR (on pourra s'inspirer de la gestion du break).

C'est un ajout au langage qui ne nécessite pas d'enrichir l'IR ni les étapes suivantes.