Projet de compilation (Étape 4)

Samuel Tardieu

SE202 - Année scolaire 2016/2017

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 se202
(se202)% 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 :

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 :

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 :

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

Les nœuds de l'IR

Les nœuds de l'IR

Les nœuds de l'IR

Les nœuds de l'IR

La structure d'une Frame

Un objet de type Frame contient :

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 :

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

En fait, il y a plus de texte que ça : les mouvements inutiles seront éliminés lors de la génération de code.

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, automake, texinfo, flex et bison si vous ne les avez pas en local.

À faire (partie 1)

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 :

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 QCM de la semaine prochaine.

À faire (partie 2)

En général, un processeur dispose d'une instruction de saut conditionnel qui permet uniquement de sauter si une condition est vraie. Si elle est fausse, l'exécution continue à l'instruction suivante. On va donc s'arranger pour qu'un saut conditionnel soit toujours suivi immédiatement par sa branche "faux".

Il va vous falloir découper chaque corps de fonction (un SEQ) dans la phase de canonisation pour :

Blocs basiques

Un bloc basique est un bloc qui :

Vous allez donc construire un ensemble de blocs basiques indexés par leur label d'entrée.

Découpage en blocs

En parcourant les instructions du SEQ qui compose la fonction, vous allez, en commençant par mettre un bloc vide comme bloc courant :

Si un bloc commence par une instruction qui n'est pas un LABEL, cette instruction ne sera jamais atteignable et peut donc être ignorée.

Détermination des traces (1/2)

Il faut maintenant déterminer les exécutions possibles pour ordonnancer les blocs au mieux. En commençant par le premier bloc déterminé lors du découpage, et en le plaçant dans une liste de blocs à examiner et en créant une liste des blocs déjà examinés :

Détermination des traces (2/2)

On pourra traiter spécialement le bloc commençant par le label de fin de fonction en le marquant comme déjà examiné et en l'insérant explicitement à la fin, mais ce n'est pas gênant s'il est traité comme les autres. Ce bloc, composé uniquement d'un label (frame.end_label) sera remplacé par l'instruction de retour du processeur cible.

Linéarisation

On peut ensuite concaténer ces blocs qui ont comme propriété que toutes les branches fausses des sauts inconditionnels reviennent à passer à l'instruction suivante.

Lorsqu'un bloc termine par un saut inconditionnel (JUMP) au bloc suivant, on supprimera ce saut inutile lors de la concaténation.

Cette concaténation deviendra le nouveau corps de la fonction (nœud SEQ).

Mais où faire cela ?

Étant donné qu'il vous est demandé de ne pas modifier tiger.py, vous devez créer cette nouvelle fonctionnalité dans la fonction reorder_blocks de ir/blocks.py.

Cette fonction dont vous devez donner le corps reçoit deux paramètres :

Elle doit retourner une nouvelle SEQ qui représente la même fonction dont les instructions ont été réordonnées selon les critères demandés.

Travail supplémentaire

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

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

La suite

Dans les séances suivantes, nous aurons à choisir les instructions assembleur correspondant à notre arbre IR pour pouvoir générer du code conforme à l'ABI ARM.

Nous générerons du code pour un nombre infini de registres, puis procèderons à l'allocation de registres pour utiliser les registres physiques ou, lorsque ça sera nécessaire, la pile.