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:
  1. 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).
  2. Les fonctions: les fonctions sont toutes globales et on ne peut pas déclarer de fonction dans des fonctions.
  3. Les expressions:
  4. Les instructions:
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): 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: 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):