Dans l’article précédent, nous avons créé un Analyseur sématique. Nous allons maintenant transformer cette analyse en code exécutable.

 

Génération en bas niveau

Le but du compilateur est de générer un langage de bas niveau, du MSIL dans notre cas.

La stratégie est de transformer votre arbre syntaxique en suite d’instructions MSIL. MSIL intègre une notion de type et méthode, nous allons donc générer un arbre avec des classes et des méthodes.

Une fois que l’on a notre arbre MSIL, il restera à générer l’assembly grâce à la création d’assembly dynamique.

Pour générer du MSIL, il faut comprendre que l’on est à un niveau proche du processeur. Ainsi pour faire une addition entre deux entiers, il faut charger un entier dans le premier registre et le deuxième entier dans le deuxième registre. Il faut ensuite procéder à l’instruction d’additions. Le résultat est dans le premier registre. Nous allons donc devoir faire des Ldloc, cela va permettre de charger la valeur d’une variable en haut de la pile. Ce qui donne pour une addition :

<br />
Ldloc.1<br />
Ldloc.2<br />
Add<br />
Stloc 0<br />

Pour l’addition, nous prenons la valeur de la variable 1 et la valeur de la variable 2. Puis le résultat est stocké dans la variable 0.

Il reste à parcourir les deux sous-arbres pour générer le code MSIL. Pour le premier sous-arbre, nous allons demander de mettre la valeur de retour dans la variable 1. Et pour le deuxième sous-arbre, nous allons mettre la valeur de retour dans la variable 2.

Alors nous allons ensuite évaluer la première branche dans une variable générée automatiquement. Puis faire la même chose avec la deuxième branche. Ce qui donnera pour un arbre TypedInt(5) :

<br />
Ldc.i4 5<br />
Stloc 1<br />

Première instruction, nous chargeons la valeur 5 dans la pile. Puis la deuxième instruction charge la valeur en haut de la pile dans la variable 1.

Si je prends l’exemple de l’addition de deux entiers, j’obtiens le code suivant :

<br />
Ldc.i4 3<br />
Stloc 1<br />
Ldc.i4 5<br />
Stloc 2<br />
Ldloc 1<br />
Ldloc 2<br />
Add<br />
Stloc 0<br />

Nous pouvons voir que nous faisons appel à beaucoup de variables intermédiaires pour faire notre addition. A chaque nœud, nous allons créer des variables intermédiaires pour stocker le résultat de notre nœud. L’idée est de générer des instructions sans se préoccuper de l’espace de stockage ou du nombre d’instructions appelées.

L’idée pour générer le MSIL est de convertir notre arbre syntaxique typé en arbre syntaxique MSIL. Voici l’arbre implémenté aujourd’hui :

<br />
type IlAssembly =<br />
Assembly of string * IlType list<br />
and IlType =<br />
Class of string * IlElement list<br />
and IlParameter = string * int<br />
and IlVariable = string * TypeName * int<br />
and IlElement =<br />
| Method of IlParameter list * IlVariable list * string * IlInstruction list<br />
| EntryPoint of IlParameter list * IlVariable list * string * IlInstruction list<br />
| Field of string * TypeName<br />
and IlInstruction =<br />
| Ldc_I4 of int<br />
| Ldc_R4 of float<br />
| Stloc of int<br />
| Ldloc of int<br />
| Stfld  of string * string<br />
| Newobj of string<br />
| Add<br />
| Ret<br />
| Nop<br />

Dans cet arbre, nous retrouvons la notion d’assembly, classes, méthodes, etc. Pour le contenu des méthodes en revanche, nous allons retrouver une liste d’instructions.

L’implémentation en F# est similaire à ce que nous avons déjà fait. Nous allons parcourir notre arbre avec la pattern matching. Par exemple, quand nous allons tomber sur l’addition :

<br />
| TypedAdd(t, e1, e2) -&gt;<br />
let var1 = returnVar + 1<br />
let var2 = returnVar + 2<br />
let variables = List.append variables [(&quot;&quot;, t, var1);(&quot;&quot;, t, var2)]<br />
let (variables, instr1) = (toIlExpression e1 variables var1)<br />
let (variables, instr2) = (toIlExpression e2 variables var2)<br />
let instr = List.append instr1 instr2<br />
in (variables, (List.append instr [Ldloc(var1); Ldloc(var2); Add ; Stloc(returnVar)]))<br />

Les trois premières lignes permettent de générer deux variables qui vont stocker les valeurs de retour des deux sous-arbres d’expression.

Nous allons ensuite générer les instructions des sous-arbres expression de gauche et celui de droite. Nous allons retrouver dans « instr » la liste des instructions pour les deux sous-arbres d’expression. A cette liste d’instruction, nous allons ajouter les quatre instructions vues précédemment pour faire une addition.

Nous allons renvoyer deux choses :

  • une liste variable qui nous permet d’exécuter le code MSIL généré. La liste est un tuplet de trois éléments :
    • un nom (vide si c’est une variable intermédiaire)
    • le type de la variable à créer
    • un numéro unique incrémenté.
  • la liste des instructions MSIL générées.

 

Optimisation MSIL

Maintenant que nous avons généré une suite d’instructions MSIL, nous voyons en regardant les instructions, qu’il est possible de faire des optimisations pour améliorer les performances du langage.

Si nous avons par exemple :

<br />
Stloc 3<br />
Ldloc 3<br />

Il faut aussi vérifier que dans la suite du code nous n’avons plus de « Ldloc 3 ». Dans ce cas-là, nous pouvons facilement enlever les deux instructions.

Dans l’étape précédente, nous avons généré beaucoup d’instructions sans regarder l’utilisation des variables. L’idée était de ne pas se préoccuper des problématiques pour transmettre les valeurs entre les différentes instructions. Avec cette étape, nous réduisons le nombre d’instructions et de variables pour stocker les valeurs intermédiaires.

 

Builder

Le builder est la dernière partie de notre compilateur. Nous allons la faire en deux étapes :

  • créer des builders pour toutes les classes, méthodes, champs, variables, etc.
  • utiliser ces builders pour appeler les instructions.

Quand nous faisons un appel à un champ de classe, nous avons besoin de passer le FieldInfo en paramètre à la méthode « Emit ». Pour cela, il faut créer la définition de la classe et des champs associés. C’est pour cela que la première étape va créer le FieldBuilder. Elle permet d’avoir une référence vers la définition du champ au moment où nous générons les instructions MSIL.

<br />
and buildEmitIl e ilGenerator locals classes members =    match e with    <br />
| Nop -&gt; ilGenerator.Emit(OpCodes.Nop)    <br />
| Ldc_I4(i) -&gt; ilGenerator.Emit(OpCodes.Ldc_I4, i)    <br />
| Ldc_R4(i) -&gt; ilGenerator.Emit(OpCodes.Ldc_R4, i)    <br />
| Stloc(index) -&gt; ilGenerator.Emit(OpCodes.Stloc, ((findLocal locals index):LocalBuilder))    <br />
| Ldloc(index) -&gt;; ilGenerator.Emit(OpCodes.Ldloc, ((findLocal locals index):LocalBuilder))    <br />
| Stfld(className, name) -&gt; ilGenerator.Emit(OpCodes.Stfld, ((findField classes className name):FieldBuilder))    <br />
| Newobj(name) -&gt; ilGenerator.Emit(OpCodes.Newobj, ((findTypeConstructor classes name).GetConstructor([||])))    <br />
| Add -&gt; ilGenerator.Emit(OpCodes.Add)    | Ret -&gt; ilGenerator.Emit(OpCodes.Ret)<br />

Ainsi, quand nous tombons sur une instruction, la méthode « Emit » est appelée pour générer l’opération associée. Dans le cas de LdLoc par exemple, le « LocalBuilder » est indispensable pour générer l’instruction. Du coup, il faut appeler la méthode « findLocal » pour récupérer le « FieldBuilder » précédemment créé et l’associer au numéro de la variable (« index »).

De même pour les opérations :

  • Stfld qui permet de stocker dans un champ de classe. Nous cherchons le FieldBuilder associé.
  • Newobj qui permet de créer une instance d’objet. Nous cherchons le constructeur par défaut du TypeBuilder associé.

Il nous faut sauvegarder notre assemblie exécutable pour la créer :

(buildAssembly a:AssemblyBuilder).Save(assemblyOutput, PortableExecutableKinds.Preferred32Bit, ImageFileMachine.I386)<br />

Le buildAssembly renvoie notre AssemblyBuilder avec tous nos types et méthodes créés. Il suffit de faire un Save en préférence 32bit pour une machine de type I386.

Conclusion

En décortiquant un compilateur, nous voyons que chaque phase est indépendante. Dans un grand nombre de cas, ces phases peuvent être utilisées pour répondre à un besoin particulier. Par exemple, le principe de construire un arbre syntaxique pour parcourir un fichier, permet de bien différentier la partie lecture, de la partie analyse de ce dernier.

Nous avons vu toutes les parties importantes d’un compilateur. Un compilateur est quelque chose de compliqué. Mais nous avons vu que les concepts de base sont simples. La difficulté est de définir notre langage. Plus nous allons chercher à faire un langage complexe, plus notre compilateur devra être complexe. Par exemple, l’inférence de type demande au compilateur de faire tout le travail pour vérifier si notre langage est sémantiquement correct. La seule chose que nous n’avons pas regardé est la gestion des erreurs. Ainsi, il faudrait stocker pour chaque nœud de notre arbre la ligne et la colonne, ce qui nous permettrait de renvoyer l’emplacement des erreurs. De plus, les compilateurs modernes ne s’arrêtent pas sur la première erreur, ils continuent à vérifier les erreurs.

Le code complet du compilateur est disponible en open source sur https://github.com/swoog/Kiss. Ce compilateur est loin d’être terminé, il reste beaucoup de cas à générer. Grâce à F# les cas manquants sont les warnings indiquant les matching manquants dans les parcours des arbres syntaxiques. De plus, le compilateur est développé en TDD ce qui me permet de valider chaque phase du compilateur sans régression.