Projects

Chaque étudiant doit choisir son projet parmis ceux proposés. Un seul projet par personne et une seule personne par projet.
Les projets sont classés en 3 catégories, facile, notés sur un maximum de 12, assez facile avec un maximum à 16 et moins facile avec un maxium à 20.
Les projets sont à réaliser soit en utilisant l'interpréteur vu lors des 3 premières scéances de TDs, l'Engine vu lors des 3 dernières scéances ou sans utiliser ni l'un ni l'autre.

Les projets doivent être rendu avant le 31 mars 2013 à 23h59 sous forme d'un fichier ZIP (pas RAR ou autre), envoyé à mon adresse mail et contenant en plus des sources de votre projet, un ensemble d'au moins 5 scripts différents montrant que l'algorithme demander fonctionne ainsi qu'un rapport d'une quinzaine de pages en PDF détaillant dans une première section, le fonctionnement de l'algorithme en termes généraux (référence aux algorithmes similaires obligatoire !) et indiquant pour chaque script, la façon dont l'algorithme se comporte (dessins obligatoires !) puis une seconde section détaillant l'organisation du code correspondant à l'algorithme ainsi que les problèmes et/ou choix liés à l'implantations.

Le but de ce projet est d'implanter un petit GC générationnel [1] en remplacement du GC implanter lors de la 3ième scéance de TD.
Le GC générationnel découpe le tas en 3 zones, les deux premières sont les zones contenant respectivement la génération 1 (ou gen1) et la génération 2 (gen2), la dernière zone "tenure" contient l'ensemble des objets ayant survécu à deux collections successives.
L'idée est d'abord d'allouer les objets dans la zone gen1, lorsque celle-ci est pleine, les objets vivant sont recopier dans la zone gen2, soi celle-ci est pleine à son tour, les objets sont déplacés dans la zone "tenure", cette zone est garbage collecté en utilisant l'algorithme du LISP2 vu lors du 3ième TD (lors du compact, on calcul les adresses destinations puis on bouge tous les objets).
Pour les zones gen1 et gen2, comme on copie les objets d'une zone à l'autre, les objets n'ont pas besoin de stocker un pointeur à utiliser pendant le GC, donc la taille du header des objets doit être uniquement la taille de la référence sur la classe. Lorsque les objets sont stockés dans la zone tenure, il faudra donc réserver en plus de la place pour un objet, la place pour la référence (avant ou après l'objet, à vous de voir) dont à besoin l'algorithme de GC du LISP2.
[1] https://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29

Le but de ce projet est de modifier le GC vu lors du 3ième cours pour que l'étape de marquage soit façon de façon concurrente [1] avec l'exécution du programme.
Lors du démarrage de l'interpreteur, celui-ci lance un thread qui servira au marquage. Par défaut ce thread est en attente. Lorsque le tas arrive à 75% d'occupation, le thread effectue le marquage des objets et tout objet nouvellement crée est considérer comme marqué.
Lorsque le GC se déclenche, il attend la fin du marquage par la thread de marquage si nécessaire et bouge les objets en mémoire.
[1] https://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29

Le but d'accélerer l'exécution d'un interpreteur, une technique habituelle consiste à ré-écrire certaine instruction pour que celle-ci s'exécute plus rapidement. C'est ce que l'on se propose de faire avec l'instruction GET_FIELD.
L'instruction GET_FIELD est assez lente car celle-ci demande à chaque appel de trouver le objet classe correspondant à l'instance en sommet de pile, puis de chercher le champs par son nom dans la classe pour trouver l'offset qui permettra d'aller lire le champ de l'objet.
Pour accélerer les choses, l'idée est réserver une place supplémentaire dans chaque instruction GET_FIELD pour que si on demande le champ d'une instance d'une classe précédemment rencontré, l'index correspondant soit directement stocké dans l'instruction. En fait, c'est le même principe qu'un inlining cache, si on appel la même instruction avec des instances d'une même classe, l'index d'offset du champ n'a pas besoin d'être recalculé.

Le but de ce projet est d'ajouter une nouvelle syntax à Small permettant de référencer des fonctions directement dans le code.
La nouvelle syntax est composé de deux partie, '::' qui permet de chargé une réfernce sur une fonction sur la pile et '.call' qui est une méthode spéciale (comme print est une fonction spéciale) qui permet d'exécuter une fonction stocké sur la pile.

          def fun(x):
            x + 3
            
          a = ::fun         // a contient une référence sur la fonction
          print(a.call(2)) // affiche 5 
        

Le but de ce projet est donc de modifier la grammaire de Small pour introduire la syntaxe '::' et de modifier l'interpreteur de Small pour qu'il exécute les syntaxes '::' et '.call'.

Le but est d'ajouter une instruction morph à l'interpreteur du langage Small. L'instruction morph est une instruction qui permet de changer dynamiquement la classe d'une instance vers une autre classe.
La syntaxe est la suivante:

          morph instance class function  
        

qui change la classe de l'instance spécifié pour la classe class en utilisant la fonction function pour indiqué la façon dont les champs sont mis à jour.
Par exemple, le code suivant transforme une instance de A en instance de B.

          classdef A(x)
          classdef B(z)
          
          def fun(a, b):
            b.y = a.x + 1
            
          def main():
            a = A(3)
            print(a.x)      // 3
            morph a B fun   // 'a' become an instance of 'B'
            print(a.y)      // 4
        

Note d'implantation: il faut penser au cas ou les instances des classes A et B ont des tailles différentes.

Le but de ce projet est d'implanter l'optimisation tail-call dans l'interpreteur de Small.
Il faut dans un premier temps, reconnaitre les méthodes ayant une récursivité terminal et donc succeptible d'être optimisé, puis dans un second temps, implanter l'optimisation [1][2] tail-call.
[1] https://en.wikipedia.org/wiki/Tail_call
[2] http://www.ssw.uni-linz.ac.at/Research/Papers/Schwaighofer09Master/

Le but est de modifier l'Engine2 pour que le calcul du maxStack et maxLocals [1] soit fait lors de l'étape de génération en utilisant un algorithme linéaire plutôt que en laissant la bibliothèque ASM faire la travail avec un algorithme en temps exponentiel.
[1] http://download.forge.objectweb.org/asm/asm4-guide.pdf

Le but est de modifier la façon dont l'Engine2 accède aux champs des objets.
Actuellement, le runtime de Small nommé Engine2 génère une serie de GuardWithTest dont l'ordre dépend de l'ordre dans lequel les classes du receveur ont été vu pour la première fois.
L'idée de ce projet consiste à monitorer le nombre de fois que chaque branche des GuardWithTest est utilisée puis lorsque le nombre d'accès total pour une instruction d'accès au champ dépasse 999 de ré-ordonner les GuardWithTest en fonction de leur fréquence d'utilisation (le plus fréquent en premier).

Actuellement le générateur de bytecode de l'Engine2 est assez basique, par exemple pour l'expression x + 1, le code générer est le suivant

          aload 0
          invokedynamic "1" ()Ljava/lang/Object; bsm_const 1
          invokedynamic "ADD" (Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object; bsm_binary
        

Donc, 1 est boxé en un Integer pour ensuite être unboxé pour effectuer l'opération +.
Le but de ce projet est de modifier le générateur de code pour opérations unaires et binaires dans le cas où un des paramètres est une constante (note: 2 + 3 est une constante, donc x + 2 + 3 est optimisable). Le générateur de code devra dans un premier temps, reconnaitre et calculer si nécessaire les constantes puis générer un bytecode Java plus efficace.
En reprenant l'exemple, le code généré devrait être

         aload 0
         iconst_1
         invokedynamic "ADD" (Ljava/lang/Object;I)Ljava/lang/Object; bsm_binary
       

La grammaire actuelle du langage Small ne définie pas les opérations booléens paresseux classique que sont le && et le ||.
Le but de ce projet est de modifier la grammaire de Small pour supporter ces deux opérateurs puis d'implanter ceux-ci dans l'Engine2.

L'idée de ce projet est de permettre à un utilisateur d'ajouter des informations de type au langage small. Tous les variables locales et paramètre dont le nom commence par '$', devra être considérer lors de l'exécution comme un entier, et donc optimizable comme tel. De plus, les fonctions dont le nom commence par '$' sera une fonction dont la valeur de retour est un entier
Par exemple, le code suivant

          def fun($n, x):
            x + 2
            $a = $n + 2 
            b = $n + 2
            $c = x
            d = $n
        

sera traduit en

          static Object fun(int n, Object x) {
            aload_1
            iconst_2
            invokedynamic "ADD" (Ljava/lang/Object;I)V
          
            iload 0
            iconst 2
            iadd
            istore 2
            
            iload_0
            iconst_2
            invokedynamic "ADD" (II)Ljava/lang/Object;
            astore 3
            
            aload 1
            invokedynamic "convert" (java/lang/Object;)I
            istore 4
            
            iload 0
            invokedynamic "convert" (I)java/lang/Object;
            astore 5
          }
        

Le projet consiste donc à modifier la grammaire de Small pour supporter les identifiant commençant par '$' puis à modifier la génération de code pour que les variables (et fonction) dont le nom commençant par un '$' soit considérer comme des entiers (ou retournant un entier) et de propager les informations de type lors d'une assignation de la gauche vers la droite et lors d'une opération binaire des arguments vers les valeurs de retour.

La grammaire actuelle du langage Small ne définie pas de façon de faire des boucles.
Le but de ce projet est de modifier la grammaire de Small pour ajouter la syntax suivante

          x = 0
          x < 10 @(
            print(x)
            x = x + 1
          |)
        

qui affiche les nombres de 0 à 9.
De plus, comme chaque instruction Small est en fait une expression, il doit être possible d'écrire la fonction cumulate ci-dessous

          def cumulate(start, end):
            sum = 0
            i = start
            i < end @(
              i = i + 1
              sum = sum + start
            |
              0   // si start >= end, the result value is 0  
            )
        

Enfin, il faut modfier le générateur de bytecode de l'Engine2 pour que celui-ci puisse exécuter des boucles.

Actuellement, l'Engine Java peut être plus lent que l'interpreteur car ce dernier utilise des tag-pointer pour représenter les valeurs de type primitif et donc évite les boxing inutiles.
Le but de ce projet consiste à générer deux variables Java pour chaque variable Small, une première variable de type Objet et une second variable de type int. Si la valeur est un entier, la variable de type Objet sera null et la variable de type int contiendra la valeur entier, sinon, la variable de type Objet contiendra la valeur.
Pour la pile, une valeur Small sur la pile consistera à deux valeurs sur la pile Java, le sommet de pile contiendra la valeur de type Objet et la case en dessous contiendra la valeur entière (avec la même convention que pour les variables).
Ce codage devrait permettre pour les opérations unaires et binaire d'exécuter par exemple un + entre deux entiers sans boxing/unboxing si les deux valeurs sont elles mêmes des entiers.
Enfin, comme la machine virtuelle ne permet de que de retourner une unique valeur, une classe spéciale nommé Tuple sera utiliser pour stocker les deux valeurs lors d'un retour d'appel de fonction.
Par exemple, le code ci-dessous

          def fun(x, y):
            x + y
            
          def main():
            print(fun(2, 3))
            
        

sera représenter par le bytecode Java suivant

          static int fun(int xi, Object xo, int yi, Object yo) {
            // load x
            aload 0
            aload 1
            
            // load y
            aload 2
            aload 3
            
            // add
            dup
            ifnonnull :L1
            pop
            swap
            ifnonnull :L2
            pop
            iadd
            aconst_null
            goto :L3
          L1:
            invokedynamic "ADD_IOIO" (ILjava/lang/Object;ILjava/lang/Object;)LTuple;
            goto :L4
          L2:
            invokedynamic "ADD_IIO" (Ljava/lang/Object;II)LTuple;  
          L4:
            dup
            GETFIELD Tuple.primtitive I
            GETFIELD Typle.object Ljava/lang/Object;
            
            // return
            new Tuple
            dup
            invokespecial Tuple.<init> ((Ljava/lang/Object;I)V
            areturn
          }
          
          static void main() {
            iconst_2
            aconst_null
            iconst_3
            aconst_null
            invokedynamic "fun" (ILjava/lang/Object;ILjava/lang/Object;)LTuple;
            dup
            GETFIELD Tuple.primtitive I
            GETFIELD Typle.object Ljava/lang/Object;
            invokedynamic "print" (ILjava/lang/Object;)LTuple;
          }
        

Le but de ce projet consiste implanter l'algorithme d'allocation de register "Iterated Register Coalescing".
[1] http://www.cs.purdue.edu/homes/hosking/502/george.pdf

Le but de ce projet consiste implanter l'algorithme d'allocation de register "Linear Scan".
[1] http://www.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf3

Le but de ce projet est d'implanter un algorithme calculant si une fonction du langage Small est pure ou non, une fonction pure est une fonction qui ne fait pas d'effet de bord, puis lors de l'exécution de ne calculer le résultat de fonctions pures ayant 1 seul argument qu'une unique fois par valeur d'argument.
Par exemple la fonction de fibonacci définie si dessous est pure

          def fibo(n):
            n < 2?(1 | fibo(n -2) + fibo(n - 1)) 
        

donc celle-ci doit s'exécuter en temps linéaire car fibo(1), fibo(2) etc doivent chacun être calculer une unique fois.
Attention, une fonctions qui alloue un objet, appel une méthode (car elle dépend de SET_METH) utilise print, etc. n'est pas pure et une fonction qui dépend elle même du fonction non pure est non pure.

Le but de ce projet est de porter le langage Small en JavaScript.
L'idée consiste au lieu de générer directement du JavaScript (ce qui n'est pas facile vu la sémantique de Javascript) à générer du bitcode LLVM [1] sous forme textuelle à partir du langage Small puis d'utiliser Emscripten [2] pour transformer le bitcode LLVM en Javascript.
Comme LLVM n'offre pas de support pour les langages dynamiques, il vous est demandé de porter uniquement la partie fonctionnel du langage Small (pas les objets, pas les méthodes, pas le GC).
[1] http://www.llvm.org/
[2] https://github.com/kripken/emscripten

Le but de ce projet est de porter le langage Small en C.
L'idée consiste à générer du code C à partir du langage Small, le code généré sera ensuite compilé par GCC dans le butde créer un exécutable.
Small étant un langage qui a des constructions dynamiques, l'accès aux champs, l'appel de méthode, algorithme de GC, etc. Il faudra aussi écrire une bibliothèque de support en C implantant les différents algorithmes dont le code C généré aura besoin.
[1] http://gcc.gnu.org/

Le but de ce projet est d'implanter un algorithme d'escape analysis [1][2] permettant de savoir quel sont les objets qui peuvent être allouer sur la pile au lieu d'être allouer dans le tas.
Le but ce ce projet est juste de sortir une liste de tous les sites allocation d'objet qui sont succeptibles d'être optimisé et non d'effectuer l'optimisation en elle même.
[1] https://en.wikipedia.org/wiki/Escape_analysis
[2] https://dl.acm.org/citation.cfm?id=320386