Extended C Compiler (ECC)
Le but de ce projet est de réaliser un compilateur d'un langage
impératif proche du C. Ce travail sera à réaliser par groupes de 4. Un
langage minimum vous est proposé, et vous devez proposer une extension
à ce langage. 4 extensions vous sont proposées dans la suite, mais
vous êtes libres d'en définir une nouvelle.
La grammaire et l'analyseur syntaxique pour le langage commun sont
fournis pour lex et yacc et pour une programmation C, mais vous pouvez
choisir tout autre langage que le C et d'autres outils que lex et yacc
(en python, java, ...). Voir
sur cette
page pour des alternatives.
1- Le langage commun
Ce langage constitue le socle commun au
langage que vous devez proposer. Une grammaire yacc et un analyseur
syntaxique pour lex sont fournis, ainsi qu'un répertoire de test. Les
tests fournis doivent pouvoir fonctionner avec votre langage étendu.
Descriptif
Le langage d'entrée est basé sur du C. En cas d'ambiguité sur la façon
d'interpréter le langage, on se ramènera au C. En plus des
contraintes imposées par la grammaire, on vérifiera les contraintes
sémantiques, notamment de type, suivantes:
- Les types: les types de base sont void, int et float. Les types
construits sont les tableaux et les fonctions. Les tableaux ne peuvent
être que des tableaux à une dimension, de taille quelconque. Les
tableaux peuvent être alloués statiquement ou dynamiquement. Ils
peuvent être déclarés soit comme des pointeurs soit comme des tableaux
(alloués statiquement dans ce cas).
- Les fonctions: les fonctions sont toutes globales et on ne peut pas
déclarer de fonction dans des fonctions.
- Les paramètres: Dans une définition de fonction, les paramètres
peuvent être des tableaux, des entiers ou des flottants.
- Il est possible de déclarer des fonctions sans les définir. Cela permet de déclarer et d'appeler des fonctions qui seront définies par des bibliothèques externes. On veuillera à respecter le protocole d'appel afin de permettre cette fonctionnalité.
- Les fonctions \texttt{printiint(int)} et \texttt{printfloat(float)} seront connues par l'utilisateur et pourront être utilisées sans déclaration dans un programme. Elles affichent respectivement un entier ou un flottant sur la sortie standard.
- Les expressions:
- Les operations: les règles de typage sont celles du C. Par ailleurs, on interdira les calculs sur les pointeurs.
- Les instructions:
- L'affectation: comme en C. Dans une affectation, un pointeur peut prendre la valeur soit d'un autre pointeur, soit d'un tableau défini statiquement. Un tableau statique (déclaré avec
t[cste]
) ne pourra être à gauche de l'affectation.
- Les boucles: les boucles for et while se comportent comme les boucles C
- Un bloc d'instructions: comme en C
- Le if: la conditionnelle if pourra avoir ou non une partie else.
La grammaire complète ainsi que
l'analyseur lexical correspondant
décrivant le langage d'entrée sont donnés. L'ensemble des sources fournies (parser, scanner, Makefile, tests) est dans l'archive srcs.tgz.
Génération de code assembleur
Le code généré sera du code
assembleur x86, pour machine Intel/AMD 64 bits. On utilisera les
instructions AVX pour toute la manipulation des types flottants.
Les instructions x86 sont détaillées dans
cette table (avec la syntaxe gcc). Pour les calculs sur les entiers et les adresses, on pourra utiliser les registres 64 bits comme indiqués dans la table. Pour les calculs flottants, on utilisera les instructions vectorielles scalaires (un seul élément dans le vecteur). La documentation complète des instructions assembleur est accessible sur le site Intel.
Le code assembleur devra pouvoir être transformé en binaire à l'aide
de as
, l'assembleur de gcc par défaut.
2- Extensions au langage
Chaque groupe devra proposer une extension au langage précédent. Ces extensions sont libres et feront l'object d'un premier rapport. Il est possible de choisir parmi l'une des extensions suivantes, ou bien d'en créer une nouvelle.
Boucle for parallèles
On ajoutera une instruction
#pragma omp parallel for
à placer devant une boucle for et permettant de créer du parallélisme de threads. Cette syntaxe s'inspire directement du langage de directives OpenMP. Le principe est de répartir les itérations de la boucle suivant le pragma entre différents threads. Le nombre de thread est laissé à votre appréciation.
Pour le code suivant:
#pragma omp parallel for
for (i=0; i<10; i=i+1) {
(Statement)
}
par exemple avec deux threads donnera une exécution où le premier thread exécutera les 5 premières itérations de la boucle, le 2ième thread les 5 dernières. Pour simplifier l'exécution, les bornes de la boucle for ainsi que l'incrément de la boucle devront être constants afin d'être connues à la compilation.
Pour la mise en oeuvre du parallélisme, on utilisera la bibliothèque pthreads. Les threads devront se synchroniser à la fin de la boucle (ou terminer).
Boucles for vectorielles
On ajoutera 2 instructions, sous forme de pragmas:
#pragma omp simd
#pragma omp simd reduction(+: id)
à placer devant une boucle for que le compilateur devra alors vectoriser. Ces pragma existent pour le langage OpenMP. Pour simplifier, on supposera que la boucle aura la forme:
for (i=cst; i<cst; i++) (Statement)
avec i
un nom de variable quelconque et cst
des constantes entières quelconques. Cette vérification sera à faire par l'analyse sémantique. Tous les calculs sur des éléments de tableaux dans la boucle ne se feront pas élément par élément mais plutot par vecteurs (en AVX). La boucle ne devra comporter que des affectations. Par exemple, la boucle:
int a[1000],b[1000],c[1000];
#pragma omp simd
for (i=0; i<1000; i++) {
a[i] = b[i] + c[i];
b[i] = c[i] * 2;
}
fera le calcul 8 éléments par 8 éléments en AVX. On pourra s'inspirer du code généré par gcc en utilisant ce pragma.
Pour le second pragma, id
est le nom d'une variable scalaire (int ou float) et l'une des instructions de la boucle devra être de la forme:
id = id + a[i];
avec a
un tableau.
Vérification statique et dynamique du code
Pour tout accès à un tableau, le compilateur devra générer un code vérifiant que tout accès à un tableau se fait bien dans les bornes de ce tableau. Il n'y a pas de modification de langage pour cette extension, il s'agit uniquement d'une protection mise en place par le compilateur lors de la génération de code.
Par ailleurs, le compilateur devra vérifier que pour toutes les fonctions retournant un type non void, quelque soit le chemin d'exécution pris dans la fonction, un return est fait.
Pour la vérification des tableaux, on pourra s'inspirer du langage Java et prefixer tous les tableaux par le nombre d'éléments qu'ils contiennent. On pourra également surcharger les fonctions malloc, realloc et free afin de gérer cette difference. Cette vérification devra également s'appliquer sur les tableaux statiques.
Si un index dépasse les bornes du tableau, une erreur devra être
générée, avec le numéro de la ligne de code source responsable du
dépassement et la valeur de l'index causant cette erreur.
Ainsi:
float a[100];
int i;
for (i=0; i<=100; i++)
a[i] = 0;
causera une erreur pour l'indice 100
.
Pour la vérification des chemins d'exécution, il s'agit d'une analyse à la compilation. Sur l'exemple suivant:
int f(int x;) {
int y;
y=5;
if (x==y) {
x=x+1;
return x;
} else if (x<y+4) {
return x+y;
}
}
devra retourner une erreur car si x!=y && x>=y+4
, aucun return n'est fait.
Ajout d'une couche objet
On ajoutera une couche objet au langage. On pourra déclarer des classes et construire des objets appartenant à ces classes. Les objets pourront disposer de variables d'instance et de méthodes. On ne considèrera pas d'héritage ni de variables ou méthodes statiques.
Pour ce faire, on apportera les modifications suivantes à la grammaire:
Par ailleurs, le compilateur donnera un sens spécial à une fonction et une variable (la grammaire n'a pas besoin d'être modifiée en ce sens):
- Une fonction prédéfinie,
new(classname)
sera
prédéfinie par le compilateur pour définir un nouvel objet de la classe classname
. On utilisera cette bibliothèque de garbage collector (GC) afin de gérer automatiquement (sans free) les allocations et désallocations.
- Une variable préféfinie,
this
, utilisable dans les méthodes. Cette variable se réfère à l'objet.
Pour la génération de code, les objets pourront être générés comme
pointeurs sur des structures (ou des tableaux), contenant les
variables d'instances ainsi que les pointeurs vers les méthodes de la
classe. Lorsqu'un objet appelle une méthode, il est en réalité passé en premier
paramètre de cette méthode et est accessible par la
variable this
.
3- A Faire
La réalisation du compilateur donnera lieu à deux livrables:
- Un rapport et une archive de programmes tests. Le rapport présentera brièvement l'extension proposée ainsi que les tests. Une dizaine de tests pour l'extension sont attendus. Le rendu est à faire pour le 10 décembre 2014.
- Une archive avec les sources de votre compilateur. Le compilateur doit pouvoir compiler sur les machines de l'enseignement. Le makefile doit être fonctionnel. Ce rendu est à faire pour le 6 janvier.
Par ailleurs, une mini-soutenance de 5min par groupe aura lieu après le rendu du projet.
L'évaluation sera basée sur ces critères (dans cet
ordre, du plus important au moins important):
- Le compilateur fonctionne pour l'ensemble de ces fonctionnalités et genère un code correct.
- La stabilité du compilateur (pas de plantage lors de la compilation)
- La qualité des rapports.
- Les fonctionnalités facultatives implémentées.