:: Enseignements :: Master :: M2 :: 2011-2012 :: Machine Virtuelle (et bazard autour ...) ::

---

Lab 3

---

Compilateur

Cette section regroupe les sujets ayant attrait à la compilation uniquement.

Throw (niveau facile)

Le but est d'implanter l'instruction throw expr dans le langage permettant de jeter une exception ayant comme message la valeur de l'expression. Il faut pour cela modifier la grammaire pour introduire l'instruction throw puis modifier le typechecker et générateur de code. On ne vous demande pas d'ajouter un catch !

Inférence de type (niveau moyen)

Le but est d'améliorer la façon dont le compilateur calcul des types des variables. Actuellement, le type est calculé en fonction de la déclaration fait par l'utilisateur et non en fonction du contexte. Par exemple, le code suivant infère que a est un any alors qu'il pourrait être inférer comme étant un int.

          var a = 2     
        

De plus, l'alorithme devra considérer que chaque affectation crée une nouvelle variable. Dans le code ci-dessous, le premier print doit être typé print(int) et le second print(double).

          var a = 2
          print(a)
          a = 3.0
          print(a)
        

Dans le cas d'un if, il faut considérer que si une variable est assigné dans une des branches, une nouvelle variable est créé après le if.

        var a = 2     // a0 est un int
        var b = 3
        if (b == 3) {
          a = 3.4     // a1 est un double 
        }             // a2 est un any
        

Dans le cas des boucles, comme on veut garder un algorithme presque linéaire, une variable déclaré avant la boucle devra être considérer comme une nouvelle variable si elle est assigné dans le corps de la boucle entre le début du corps de la boucle et l'endroit où elle est modifiée. Elle sera considérer comme une autre variable de l'endroit où elle est assigné jusqu'à une nouvelle assignation ou la fin de la boucle. Après la boucle, la variable (ou une nouvelle) sera considéré comme any.

        var a = 2
        var b = 3
        print(a)     // print(int)
        for(var i = 0; i < 10; i = i + 1) {
          print(a)   // print(any) car peut être appelé
          a = 4.0
          print(a)   // print(double)
        }
        print(a)     // print(any)
        

En terme d'implantation cela veut dire que le corps d'une boucle pourra être typechecké au maximum 2 fois si cela est nécessaire.

Max (niveau facile)

Actuellement, le compilateur utilise la bibliothèque ASM pour calculer le nombre maximal de variables locales et la taille maximale de la pile qui sont des informations obligatoires dans le bytecode.
L'idée est de ne plus utiliser la bibliothèque ASM pour cela (elle restera utilisée pour la génération proprement dite) et de calculer ces valeurs lors de l'étape de génération.
section 3 of ASM guide

StackMap Frame (niveau facile)

Actuellement, le compilateur utilise la bibliothèque ASM pour calculer les stackmap frames qui sont des informations obligatoires dans le bytecode depuis la version 7 de Java.
L'idée est de ne plus utiliser la bibliothèque ASM pour calculer les stackmap frames. La bibliothèque restera utilisée pour générer les stackmap frames proprement dit. Il vous faudra donc calculer les stack-frames aux endroits ou ceux-ci sont requis et utiliser l'API d'ASM pour les traduires en bytecode.
Même si ce sujet peut sembler assez similaire au sujet précédent, l'algorithme n'est pas le même !
section 3.1.5 of ASM guide

Propagation des constantes (niveau facile)

Actuellement le compilateur ne propage pas les constantes, 1 + 2 est compilé

         iconst_1
         iconst_2
         iadd
       

alors que le compilateur pourrait directement remplacé le code par la valeur 3.

         iconst_3
       

Le but de ce sujet est donc d'implanter la propagation des constantes sur tout les types (true && false, "foo" + "bar, etc) ainsi que la suppression de code mort à cause de la propagation des constantes code par exemple

       if (false && true) {
         // dead code, should be removed
         print("dead code")
       }
       

Linear Scan allocator (niveau dure)

Le but est d'implanter l'algorithme d'allocation de registre linéaire pour numéroter les variables locales.
Register_allocation et Section 4 de http://www.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf

Inlining de fonctions (niveau facile)

Le but est lors de la génération d'inliner le code des petites fonctions, par exemple

         fun f(x, y) {
           return x + y
         }
         {
           print(f(2, 3))
         }
       

devra produire le même code que celui produit par

         {
           int $x = 2
           int $y = 3
           print($x + $y)
         }          
       

L'algorithme devra donc differencier les fonctions suivant leurs tailles (en nombre d'instructions) puis remplacer le code lors de la génération. L'algorithme devra être capable d'inliner avec une profondeur maximale supérieur à 1 et ne devra pas inliner les fonctions récursives. Notez que la phase de typage devra aussi être modifier légèrement car dans l'exemple ci-dessus x et y sont typés any alors que $x et $y sont typé int.

Visiteur avec des method handles (niveau facile/moyen)

Un des problème des interpreters/compilateurs et autre typecheckers est que lorsque l'on essaye d'optimizer leurs vitesse ceux-ci utilisent énormément le mécanisme de double-dispatch des visiteurs hors chacun des dispatch est megamorphic donc non-inlinable par la VM.
Le but est ici d'éviter le double-dispatch;
Il est possible de simplifier le double-dispatch pour ne faire qu'un seul dispatch car il est possible de stocker l'association entre le noeud de l'AST et la méthode à exécuter (sous forme de MethodHandle) dans une table de hachage.
Dans le cas d'un visiteur sur l'AST nous connaissons l'ensemble des types pour lequels le visiteur peut être appelé, il s'agit de tout les noeuds de l'AST, il est donc possible de précalculer la table de hachage en parcourant la classe Visitor, en récupérant le type du premier paramètre de toutes les méthodes publiques (pas protected). Puis, pour chaque type (c'est en fait toujours une classe), de trouver parmis les méthodes déclarés du visiteur courant quelle est celle qui doit être appelée.
Par exemple, la classe Visitor définie les types ExprAdd, ExprSub, etc, pour chaque classe il est possible de trouver la méthode visit de la classe du SimpleInterpreter correspondant.
Une fois l'association crée, il suffira lors de l'appel à la méthode dispatch d'appeler la méthode correspondant à la classe du premier argument et utilisant invokeExact.
Optionellement (dans ce cas le niveau de ce sujet devient moyen) il est possible de faire une implantation lazy (paresseuse) du visiteur avec une table de hachage qui au lieu de calculer quelles méthodes doient être appelées pour quels types lors de la construction du visiteur, va faire ce caclcul lors de l'appel à dispatch. Pour que le code soit efficace, le résultat de l'association devra être stocker dans la table de hachage ce qui va poser un gros problème de concurrence car si deux threads utilise deux visiteurs différents mais de la même classe, il devront utiliser la même table donc il rique d'y avoir des mutations de la table de façon concurrente. Il n'est pas souhaitable d'utiliser ici une structure de donnée concurrente comme la ConcurrentHashMap car celle-ci est basé sur des verrous et le coût d'acquisition d'un verrou va être supérieur au coût de faire le double-dispatch. L'astuce consiste à faire en sorte que les entrées dans la table de hachage soit pré-réservées de telle façon que la structure la table de hachage ne puisse pas être modifiée par des appels concurrents.

Extraction de boucle (niveau facile/moyen)

Les optimisateurs de code optimise les fonctions et les boucles. Une étapes simple qui peut être faite avec de réèlement optimiser consiste à transformer les boucles en appel de fonction pour simplier l'écriture de l'optimisateur de code.
Le but de ce sujet est de transformer les boucles en appels de fonction. Par exemple,

        {
          var int a = 0;
          var i = 0;
          for(; i < 10; i = i + 1) {
            a = a + i
          }
          print a
        }
       

devra être transformé en un code équivalent (car la transfomation se fait à la génération) à

          fun Box2 loop$0(int a, i) {
            for(; i < 10; i = i + 1) {
              a = a + i
            }
            return new Box2(a, i)
          }
          
          {
          var int a = 0;
          var i = 0;
          box = loop$0(a, i)
          a = box.get0()
          i = box.get1()
          print a
        }
       

avec Box2 une classe prédéfinie qui est construit avec deux paramètres. Il vous faudra donc coder les classes Box1, Box2, ..., Box10, etc ainsi que la classe BoxN basée sur un tableau dans le cas ou plus de 10 variables sont utilisées dans la boucle.
Optionnellement (dans ce cas le niveau devient moyen), au lieu de pré-coder les classes Box1, BoxN, celles-ci peuvent être génerées par le runtime à la demande en utilisant un invokedynamic à la place du new qui créera les classes si néccessaire.

Suppression de variables non-utilisées (niveau facile)

Le but est de ne pas générer de code dans le cas où une variable est déclarée mais pas utilisée. Par exemple, dans le code ci-dessous, b n'est pas utilisé.

          var a = 0
          var b = 3
          print(a)
        

L'algorithme devra aussi supprimer les variables utilisées mais qui dépendent uniquement de variable non-utilisé et de constantes (et d'opérations sans effet de bord). Par exemple, dans le code ci-dessous, b et a sont inutilisées.

          var a = 0
          var b = a + 3
        

L'algorithme consiste à partir de la fin des instructions et de remonté vers le début, on note les usages des variables si on voit la assignation (ou la déclaration) de la variable alors qu'elle n'a pas été utilisé, on peut la supprimer. Dans ce cas, l'expression de l'assignation (ou de la déclaration) doit être supprimer, pour notre exemple, comme b n'est pas utilisé, on ne doit pas généré le a + 3 donc a est aussi non utilisé. Pour les branches des if (ou pour les boucles), l'utilisation de la variable dans l'une des branches est suffisant.

Runtime

Cette section regroupe les sujets effectuant des modifications sur le runtime uniquement.

Détection de code chaud (niveau facile)

Le but est d'outiller le runtime pour afficher si une fonction est chaude ou pas. Exactement, il y a 4 niveaux possibles, 'never called' si la fonction n'a jamais été appelée, 'called once' si la fonction a été apellée 1 fois, 'warm' si la fonction a été appelé 1000 fois et 'hot' si la fonction a été appelée plus de 1500 fois. Le runtime devra fonctionner de la façon suivante, lors de l'exécution d'un script, le runtime doit enregistrer le nombre d'appel à chaque fonction puis à la fin du script, le runtime doit afficher un tableau (en ASCII) indiquant la chaudité (hotness) de chaque fonction. Ces informations sont donc spécifiques à une exécution donnée.

Mixed

Cette section regoupe les sujets pour lesquels il faut faire des modifications et sur le compilateur et sur le runtime

fonction comme des lambdas (niveau moyen)

Le but est de pouvoir stocker des fonctions dans des variables et d'appeler celles-ci. Le code suivant devrait donc fonctionner.

          fun identity(x) {
            return x
          }
          
          {
            var foo = identity
            print(foo)     // function: any identity(any)
            print(foo(3))  // 3
          }
        

Pour cela, il faut considérer les fonctions déclarées comme étant des variables possible, une fonction déclaré à postériori doit être visible dans le corps d'une fonction déclaré à priori. Lors de l'exécution, 'identity' doit correspondre à une objet de la classe Function (à vous de voir la relation avec la classe fr.umlv.foolang.compiler.Function). Un appel de fonction sur une variable (ici sur 'foo'), devra appeler la fonction stocker dans la variable.

lambda (niveau moyen)

Le but est d'implanter la syntaxe des lambdas dans le langage. Une lambda est une fonction anonyme définie soit par une expression (séparé par une flèche '->') soit par un block. Le code suivant doit fonctionner.

          {
            var foo = fun (x, y) -> x + y
            print(foo.call(2, 3))  // 5
            
            var bar = fun (x, y) { return x + y }
            print(bar.call(2, 3))  // 5
          }
        

En terme de code, le code de création de la lambda est généré en utilisant invokedynamic et en passant en argument à la methode de bootstrap le noeud de l'AST correspondant à la définition du lambda. Lors de l'appel à la méthode de bootstrap de invokedynamic, le code du lambda est compilé sous forme de MéthodeHandle puis stocker dans un objet de type Lambda. Lors de l'appel en utilisant call on vérifie que l'objet courant est de type Lambda et si c'est la cas, on appel sont méthode handle. Si l'objet n'est pas de type Lambda, il faudra générer une exception.

appel de paramètre nommé (niveau facile)

Le but est que l'on puisse nommé les paramètres lors de l'appel

          fun foo(a, b) {
            print(a)
            print(b)
          }
          
          {
            foo(1, 2)      // print 1 and 2
            foo(b=1, a=2)  // print 2 and 1
            foo(1, b=3)    // print 1 and 3
            foo(a=2, 3)    // doesn't compile, named parameter should be at the end
          }
        

La grammaire de foo accepte déjà les paramètres nommés, il faut juste implanter le TypeChecker et le générateur de code. Lors de l'appel, il faut passer le nom des paramètres si ceux-ci ont un nom en tant que argument de la méthode de bootstrap. A l'exécution, il faut utiliser la méthode MethodHandles.permuteArguments pour remettre les paramètres dans l'ordre avant l'appel.

Typedef et objet (niveau dure)

Le but est d'augmenter le langage foo pour permettre de déclarer des objets. On se propose d'ajouter une syntax permettant de définir à un utilisateur de définir ses propres types.

          typedef List { element, List next }
          
          {
            var list = List { element: 1, List { element: 2, null}}
            for(var l = list; l != null; l = l . next) {
              print(l.element)
            } 
            
            print(list.foo)  // error: foo is not defined
            list.foo = 3     // error: foo is not defined
          }
        

'typedef' permet de définir un type utilisateur. On peut définir des types à n'importe quel endroit où on peut définir des fonctions. Il est possible d'utiliser un type avant sa déclaration avec un typedef. La syntaxe List { element: 1, next: null } permet d'allouer une instance d'un type l'ordre entre les pair champs/valeur n'a pas d'importance. La syntax avec le '.', par exemple, l.element, permet d'accéder à un champs.
De plus, on souhaite pour des questions de performance que les classes définient par l'utilisateur soient représentées par des classes Java et que celle-ci soit créer non pas lors d'un typedef mais la première fois que la classe est instanciée.

Objet Javascript (niveau moyen)

Le but est d'augmenter le langage foo pour permettre de déclarer des objets définies par l'utilisateur. On se propose de réutiliser la syntax/sémantique de Javascript pour cela.

          {
            var list = { element: 1, { element: 2, null}}
            for(var l = list; l != null; l = l . next) {
              print(l.element)
            } 
          }
          
          print(list.foo)  // error: foo is not defined
          list.foo = 3     // ok, now list as a field foo
          print(list.foo)  // 3
        

La syntaxe { element: 1, next: null } permet d'allouer une instance d'un type sans nom. L'ordre entre les pair champs/valeur n'a pas d'importance. La syntax avec le '.', par exemple, l.element, permet d'accéder à un champs ou de modifier celui-ci. Si le champs n'existe pas pour l'instance, le champs sera créer.
L'implantation se fait en représentant les objets par des tables de hachage.

homoiconic (niveau dure)

L'idée consiste à permettre à un utilisateur de manipuler l'AST à travers le langage. Par exemple,

          fun foo(x, y) {
            return x + y
          }
        
          fun printFoo(x, y) {
            print(foo(x, y))
          }
        
          {
            printFoo(3, 4)     // compile printFoo and foo, print 7
            f = reflect foo    // drop compiled code of foo
            f.body.instr.get(0).expr.expr = reflect 2  // replace x by 2 in return x + y
            printFoo(3, 4)     // re-compile foo, print 6
          }
        

L'instruction 'reflect' suivi d'un nom d'une fonction permet d'obtenir l'AST de la fonction. L'instruction 'reflect' suivi d'une expression permet d'obtenir l'AST de cette expression. Si il y a une ambiguité car il existe une fonction foo et une variable foo le typechecker devra lever une erreur.
A l'exécution, l'instruction 'reflect' charge l'AST, l'AST est unique et toutes modifications de l'AST se répercute sur l'ensemble du programme. L'instruction 'x.property' permet d'appeler la Java x.getProperty() et l'instruction x.property = value permet d'appeler la fonction Java x.setProperty(value). L'instruction x.foo(args) permet d'appeler la méthode Java x.foo(args).
Pour simplifier la sémantique, reflect avec un nom de fonction considère que la fonction si elle a déjà été compilé, le code doit être jeter. Le prochain appel à la fonction recompilera celle-ci avec le modification de l'AST si il y a eut entre temps. Si la fonction a déjà été compilée et que l'on modifie l'AST sans appeler refect sur la fonction, alors le code n'est pas modifié.

duck typing (niveau facile)

On souhaite ajouter la possibilité de faire de la surchage (overloading) de fonction mais sur le premier paramètre uniquement, les autres devant être identique. L'idée est de pouvoir spécialiser un appel en fonction du premier paramètre, comme pour l'appel virtuelle mais sans définir d'objet (en fait comme en Modula).

          fun foo(x) {  // generic function foo
            print(x)
          }
          
          fun foo(int x) { // specilized version for int
            print("integer " + x)
          }
          
          fun bar(x) {
            foo(x)         // virtual call (bi-morphic)
          }
          
          {
            var a = 2.0
            bar(a);      // print 2.0
            a = 2
            bar(a);      // print integer 2
          }
        

L'appel de fonction peut alors être polymorphe. L'implantation doit utiliser un inlining-cache (avec autant de guardWithTest que vous voulez) mais uniquement dans le cas ou la fonction est surchargé. Sinon, l'appel de fonction doit se faire avec un site d'appel constant.

le sujet 42 (niveau trop facile)

C'est le sujet qui vous donne tout les points juste pour savoir si vous lisez les docs jusqu'au bout.
Désolé ... c'est une blague.

---