Gcc sur mesure avec MELT

GNU/Linux Magazine n° 143 | novembre 2011 | Pierre Vittet
Creative Commons
  • Actuellement 0 sur 5 étoiles
0
Merci d'avoir participé !
Vous avez déjà noté cette page, vous ne pouvez la noter qu'une fois !
Votre note a été changée, merci de votre participation !
Tout le monde connaît le compilateur Gcc, tout le monde l'utilise ! Mais Gcc est rarement exploité à la mesure de ses possibilités ! Au-delà de la multitude d'options proposées, le programmeur peut aussi développer des extensions de Gcc, et cette tâche est moins ardue qu'on ne le croit, grâce à MELT. On présentera les notions à connaître sur Gcc et l'intérêt de l'étendre via des exemples simples.

1. Introduction

1.1 La complexité de Gcc

Le compilateur Gcc (Gnu Compiler Collection) est le compilateur de référence pour les systèmes Linux et les logiciels libres. Il peut compiler du code source en C, C++, Ada, Fortran, mais aussi Java, Objective C, et même Go... Sous Linux, beaucoup de logiciels essentiels sont compilés avec Gcc : le noyau Linux, les shells comme bash et les interpréteurs comme python ou perl, les bibliothèques comme Glibc, les environnements graphiques Gnome/Gtk ou KDE/Qt, les supports d'exécution des langages de haut niveau comme Java, Ruby ou Ocaml, etc. C'est pourquoi le mouvement GNU considère Gcc comme une brique essentielle du logiciel libre ; GNU/Linux ne pourrait pas s'en passer.

Le compilateur Gcc lit du code source (en C, C++, etc.), produit du code assembleur et pilote des programmes de binutils tels que l'éditeur de liens ld ou l'assembleur as. Les tâches d'analyse syntaxique (syntax parsing) et d'émission de code assembleur (ou parfois de code machine) genéré sont communes à tous les compilateurs, même les plus petits, comme Tiny CC. Mais l'essentiel du travail de Gcc consiste en de nombreuses optimisations, pour que le code généré soit plus performant tout en respectant la sémantique du code source. Sans optimisations, un compilateur ne peut pas profiter de la puissance des processeurs actuels, car ceux-ci sont extrêmement complexes et hétérogènes ; le langage C n'est plus en 2011 un langage assez proche du code machine, comme il l'était dans les années 1980. Le code machine x86 n'est plus semblable aux processeurs AMD/Phenom ou Intel/Core i5 de nos ordinateurs : ces processeurs traduisent à la volée, et différemment, le code machine x86 en micro-opérations. C'est pourquoi un exécutable optimisé pour une machine AMD pourrait être moins efficace sur un Intel et réciproquement. Chaque cœur d'un processeur est constitué de nombreuses unités (de décodage, de calcul entier ou flottant, de cache, de prédiction de branchements, etc.) qui travaillent simultanément : l'ordonnancement (scheduling) des instructions machines devient primordial (car elles peuvent être exécutées indépendamment, en parallèle, dans un même cœur). La bonne utilisation du cache est déterminante (car l'accès à une donnée dans les barrettes de RAM est 300 fois plus lent qu'à celles dans le cache du processeur). Gcc optimise en tenant compte de tous ces aspects.

Gcc est donc un très gros logiciel (5 millions de lignes de code source), développé par une communauté importante (plusieurs centaines de développeurs à temps plein, souvent salariés de grosses entreprises comme Google, AMD, Intel, IBM, Redhat, ...). La qualité de Gcc est due à la revue systématique par les pairs : chaque modification (ou patch), même petite, du compilateur doit être approuvée par un reviewer distinct de l'auteur qui la propose. Le compilateur Gcc est auto-amorcé (bootstrapped) : il se compile lui-même pendant son installation. L'aptitude à bien se compiler lui-même est un gage de qualité : si Gcc est capable de bien compiler son propre code (qui est complexe et dont le style est hétérogène), il sera probablement capable de bien compiler le votre !

Gcc est organisé en des frontaux (« front-ends ») qui transforment le code de chaque langage source en une représentation interne commune, une imposante couche médiane (« middle-end ») qui malaxe les représentations intermédiaires ; enfin, la couche arrière (« back-end ») génère le code assembleur (qui deviendra un fichier objet). Il y a de nombreuses passes (plus de 200 !) dans Gcc où les représentations internes sont malaxées comme dans un pétrin.

Figure 1 : Gcc pétrit les représentations internes.

Il existe de nombreuses représentations internes dans Gcc (représentées par près de 2000 structures de données différentes). Les plus importantes y sont :

- Generic et Tree pour représenter la syntaxe du code source ;

- Gimple pour une représentation des instructions (à 3 adresses) ;

- basic_block pour les blocs élémentaires d'instructions Gimple ;

- edge pour les arêtes joignant des blocs.

Ces deux dernières servent (avec d'autres) à représenter le graphe de flot de contrôle qui définit l'ordre d'exécution du programme compilé.

1.2 Traiter spécifiquement du code source avec votre Gcc

Il est souvent utile de traiter du code source (et pas seulement pour le compiler en du code machine). Ces traitements pourraient se faire à l'aide du compilateur Gcc convenablement étendu : vos extensions de Gcc profiteraient alors de toute la puissance de travail du compilateur. Ces extensions spécifiques (à une entreprise, un logiciel, un projet, ...) pourraient :

- fournir des diagnostics spécifiques, par exemple signaler au développeur toutes les fonctions qui appellent fopen) sans tester son résultat ;

- effectuer un contrôle fin du typage, par exemple sous Gtk, le typage des arguments de la fonction variaire g_object_set ;

- faire des optimisations contextuelles, par exemple simplifier fprintf(stdout, ...) (éventuellement obtenu par expansion de macro ou par inlining de fonctions) en printf(...) ;

- aider à la navigation, le refactoring, la rétro-ingénierie, ou la métrique de gros logiciels sources ;

- et plus généralement, faire tous les traitements que vous imaginez qui profiteraient de la puissance de Gcc !

Ce genre d'extensions pourraient être fournies par des greffons péniblement codés en C. Ainsi, le projet Mozilla a fait, pour aider les développeurs du navigateur Firefox, le greffon TreeHydra (qui s'appuie sur Javascript) pour Gcc. Ce greffon permet de vérifier quelques règles de codage propres à ce projet.

Il existe aussi des analyseurs statiques autonomes, comme Frama-C (voir http://frama-c.com/), mais ceux-ci perturbent le cycle de développement (leur utilisateur doit lancer un outil autonome, au lieu d'ajouter des options à Gcc). Ce sont des outils très puissants, mais difficiles à utiliser, et adaptés à des cas particuliers (logiciels embarqués fortement critiques, notamment pour l'aéronautique ou le nucléaire). Il serait difficile d'utiliser Frama-C pour tous les logiciels usuels d'une distribution GNU/Linux, car il faudrait annoter, dans des commentaires utilisant le formalisme ACSL pour les spécifications et les propriétés du logiciel analysé, le code source de ces logiciels pour que Frama-C puisse en prouver la correction.

Le développement d'extensions de Gcc se heurte à plusieurs difficultés : d'abord et principalement, la complexité du compilateur Gcc ; d'autre part, les extensions doivent faire des traitements sur des données complexes - notamment trouver des motifs ou des formes particulières dans les représentations internes de Gcc, et le langage C (qu'on utilise pour coder des greffons) est peu adapté à ce genre de traitement.

MELT est un outil (disponible sur http://gcc-melt.org/, libre, sous licence GPLv3+) pour faciliter le développement d'extensions spécifiques de Gcc, en fournissant un langage dédié (domain specific language ou DSL, qu'on appelle aussi Melt) pour ce faire. Concrètement, après compilation et installation de MELT, on dispose d'un greffon melt.so pour Gcc 4.6. Il faut donc donner des arguments supplémentaires à gcc pour que MELT soit activé.

Le langage Melt a une syntaxe lispienne (dans la tradition d' Emacs Lisp ou de Guile). Une extension codée en Melt est d'abord traduite en un module MELT dynamiquement chargé par le greffon melt.so (qui appelle dlopen). Ce module est obtenu par génération de code C, ensuite compilé. Le traducteur de votre code Melt vers le code C ainsi généré est lui-même codé en Melt, et sa forme traduite en C est également distribuée (avec le code source Melt qui en est l'origine) dans l'archive source du logiciel libre MELT. À l'installation, la traduction du traducteur Melt vers C est recommencée.

L'utilisateur de MELT doit d'abord coder son extension en langage Melt. Ensuite, il doit faire générer par le greffon MELT le module correspondant, et ce module a été obtenu par compilation d'un fichier généré en C. Enfin, il va utiliser ce module, avec le greffon, pour compiler ses fichiers sources. On peut aussi faire exécuter du code Melt dans votre fichier passe.melt directement par le greffon ; dans ce cas, le greffon melt.so a chargé les modules du traducteur Melt qui ont automatiquement généré le (ou les) fichier(s) passe*.c, puis qui l'ont compilé (en lançant un make initié par gcc) en un module passe.so et l'ont chargé. Il faut donc éviter de nommer vos extensions Melt avec le même nom de base que les fichiers en C, C++, Ada, Go, ... que vous compilez avec.

Le programme gcc n'est qu'un programme lanceur qui, selon les suffixes des fichiers arguments, va lancer le compilateur proprement dit cc1 pour C, cc1plus pour C++, puis l'assembleur as sur le code produit, etc. Pour savoir ce que lance gcc, il faut lui passer l'argument -v.

L'article « Conception et vie d'un programme : les sous-traitants de Gcc » d'Alexandre Courbot (GNU/Linux Magazine France n°128, juin 2010, pages 34-42) détaille les programmes lancés par la commande gcc.

Comme les greffons de Gcc ne peuvent pas encore modifier le comportement du lanceur, il convient de compiler un fichier vide pour lancer Gcc avec MELT en tant que traducteur de votre code Melt. Ainsi, pour traduire votre passe.melt en un module MELT passe.so, il faut lancer la commande suivante (car techniquement, le traducteur MELT n'est pas un frontal de Gcc) :

gcc -fplugin=melt -fplugin-arg-melt-mode=translatetomodule \ -fplugin-arg-melt-arg=passe.melt -c -x c /dev/null

Si on dispose d'un fichier vide empty.c, on peut lancer pour faire la même traduction :

gcc -fplugin=melt -fplugin-arg-melt-mode=translatetomodule \ -fplugin-arg-melt-arg=passe.melt -c empty.c

Le traducteur de Melt vers C est rapide. Mais les commandes précédentes lancent automatiquement un make pour obtenir un module passe.so à partir des fichiers passe*.c générés. L'essentiel du temps est passé dans ce make interne, car le code C généré par MELT est souvent 20 fois plus gros que le code Melt qui en est à l'origine. En effet, Melt est un langage de haut niveau, concis et puissant. C'est là son principal intérêt !

2. Aperçu du langage Melt

2.1 Pourquoi un langage dédié lispien ?

Coder des extensions spécifiques à Gcc est difficile si on les code en C, car ce langage est très efficace, mais difficile à utiliser pour manipuler les structures de données internes, fort complexes, du compilateur. Il vaut mieux disposer d'un langage de plus haut niveau, plus expressif (même s'il est un peu moins efficace), et bien adapté aux traitements plutôt symboliques (sur des représentations internes arborescentes ou en graphe orienté) usuels à l'intérieur de tout compilateur. C'est particulièrement vrai quand on étend Gcc : l'extension (qu'elle soit un greffon natif laborieusement codé en C, ou une extension en Melt) sera utilisée moins fréquemment que Gcc et par une plus petite communauté d'utilisateurs ; aussi l'effort de développement de cette extension gagne à être diminué par l'utilisation d'un langage ad-hoc de haut niveau.

Il n'est pratiquement pas possible d'intégrer un langage de script existant (comme Python, Ruby, Lua, Guile, ou même Ocaml) dans le compilateur Gcc. En effet, ce compilateur n'a pas été conçu dans cette optique et contient de nombreuses structures de données (près de 2000 !) et des centaines de variables. La plupart des données (mais pas toutes) internes à Gcc sont gérées par un ramasse-miettes interne Ggc, très pratique mais rudimentaire, incompatible avec ceux des langages de scripts. Coller un interprète existant dans Gcc n'est pratiquement possible que si on se restreint à une minuscule partie des internes de ce compilateur, et la glue nécessaire serait rapidement obsolète avec l'évolution constante de Gcc, dont le code source croît encore de 6 % à 10 % chaque année...

La solution proposée par MELT est un langage ad-hoc, capable de manipuler aussi bien des données de Gcc que de MELT. C'est une distinction importante à faire : MELT propose ses propres types de données, qui sont typées dynamiquement (à la manière de Python ou Scheme) et gérées par le ramasse-miettes de MELT, on parle alors de valeur. Au contraire, il est parfois nécessaire de travailler sur les données élémentaires de Gcc, on parle alors de truc (ou de stuff en anglais). Dans la mesure du possible, on préfère généralement, dans du code Melt, manipuler des valeurs, mais il est indispensable de pouvoir aussi y traiter des trucs (comme les données gimple ou tree internes dans Gcc, ou tout simplement un long). Ce distinguo entre valeurs et trucs est essentiel dans MELT et constitue une originalité.

Il est aussi important de pouvoir insérer des bouts de code C dans du code Melt. Ceci permet d'utiliser facilement toute l'API interne de Gcc. C'est un peu l'analogue de la syntaxe asm dans le code C du noyau ; elle y apparaît rarement, mais on ne pourrait pas s'en passer. Le moyen le plus simple (de très bas niveau) d'insérer du C dans du Melt est l'opérateur code_chunk expliqué plus loin. Il existe aussi des constructions de plus haut niveau définissant comment transcrire vers le C des constructions en Melt.

L'avantage d'une syntaxe lispienne, c'est sa simplicité et son orthogonalité ; c'est aussi de disposer des nombreux outils qui la supportent (modes d'édition lispiens d'Emacs ou plugin Vim, par exemple, documentations, ...). L'étrangeté d'une syntaxe lispienne, c'est la multiplicité et l'importance des parenthèses (les mauvaises langues disent que Lisp est l'acronyme de « Lots of Insipid Stupid Parenthesis »). Mais on prend vite l'habitude des parenthèses. Il est recommandé d'éditer du code Melt avec un éditeur capable d'apparier rapidement une parenthèse ouvrante à sa fermante correspondante. Sous Emacs, on peut par exemple forcer le mode lispien d'édition en commençant chaque fichier source Melt par une ligne de commentaire ;; -*- lisp -*-. Un commentaire en Melt commence par un point virgule et termine à la fin de la ligne.

Tous les langages lispiens (dont Melt) partagent un même trait : les expressions sont toutes entre une paire de parenthèses, et l'opérateur est placé après la parenthèse ouvrante, suivi des opérandes et d'un parenthèse fermante. Ainsi, l'addition des trucs entiers 2 et 3 se code (+i 2 3) en Melt car l'addition entière y est l'opérateur primitif binaire +i. Les parenthèses sont toujours significatives en Melt : (f) est différent de f, car (f) est l'application (ou l'appel, ou l'invocation) de la fonction f sans arguments, tandis que f sans parenthèses est la valeur fonctionnelle (en Melt, les fonctions sont des valeurs à part entière). C'est la même distinction que f() (un appel de fonction) et f (le pointeur vers le code de la fonction) en langage C. D'ailleurs, ((+i 2 3)) est rejeté par le traducteur MELT, car on ne peut pas appliquer sans arguments le truc entier 5, qui n'est pas une valeur ! Les noms de variables (les symboles en jargon lispien) peuvent mélanger lettres et autres signes. On pourrait donc avoir une variable nommée a-b (qui n'est pas une soustraction, mais un identificateur, comme a_b peut l'être en C ou en Melt). La casse des lettres dans les symboles n'est pas significative (contrairement à C). Ainsi, +i est la même chose que +I; de même, if, If ou IF sont pareils. Les langages Scheme, Emacs Lisp, Common Lisp ont inspiré certains noms d'opérateurs essentiels de Melt comme if cond let letrec progn setq defun defclass, etc.

2.2 Quelques éléments de syntaxe en Melt

Le langage Melt est (comme Lisp, Scheme, Ocaml et d'autres) un langage construit sur des expressions qui sont évaluées en un résultat. Il n'y a donc pas d'instructions en Melt, seulement des expressions. Par exemple, la conditionnelle if renvoie un résultat (tout comme le fait l'opérateur conditionnel ternaire ?: du langage C). Ainsi, si x vaut le truc entier 2, l'expression (if (>i x 1) 3 (+i 1 x)) a pour résultat le truc entier 3. La même expression donnerait 1 si x était 0. Certaines expressions primitives renvoient un résultat vide et ne sont utiles que pour leurs effets de bord, par exemple un message de débogage. Il est aussi possible d'ignorer le résultat d'une expression. Par exemple, l'opérateur progn de Melt ignore le résultat de tous ses arguments, sauf le dernier (comme le fait la virgule dans une expression en C). Dans plusieurs constructions syntaxiques, une séquence d'expressions est évaluée en séquence, mais seul le résultat de la dernière sous-expression compte. C'est souvent le cas dans les branchements conditionnels, comme ici :

(if (>i x 1)
(progn
(debug_long “Condition is true” x)
3
)
(+i 1 x)
)

Il est possible d'avoir des variables locales en Melt. On utilise l'opérateur let suivi d'une séquence de liaisons (« bindings »). Ces liaisons sont locales au corps de l'expression let et y définissent donc des variables locales, inaccessibles à l'extérieur de ce let. Le corps du let est une séquence de sous-expressions dont la dernière renvoie le résultat du let alors que ceux des autres sont ignorés. Quand une liaison concerne un truc, pas une valeur, on y indique le type du truc par des « mots-clés » comme :long ou :gimple - les c-types de Melt. Ainsi, l'expression :

(let ((:long x 3)
(:long y (+i x 2))
)
(*i x y)
)

contient deux liaisons sur les variables locales x et y (de type truc entier) et son résultat est le truc entier 15.

Une faculté pratique de Melt est la possibilité d'inclure des fragments de code C dans du code Melt. Ces fragments sont les macro-chaînes (« macro-strings »). Alors qu'une chaîne de caractères entre double-accolades est lue en Melt comme en C de sorte que \n y est compris comme le caractère de saut à la ligne, une macro-chaîne commence par #{, et se termine par }#, mais l'antislash n'y est pas spécialement traité (car il est transcrit dans le code C généré). Le dollar signale et introduit une variable Melt dans une macro-chaîne. Cette astuce permet d'écrire naturellement des fragments de code C avec variables Melt. Ainsi, la primitive *i de multiplication de deux trucs entiers est définie par :

(defprimitive *i (:long a b) :long
:doc #{Integer binary product of $A and $B.}#
#{(($A) * ($B))}#
)

Dans une liste d'arguments formels, on donne des c-types (qui s'appliquent aux arguments suivants) et les noms des arguments. Ainsi, le premier :long qualifie les arguments a et b. Le deuxième :long qualifie le résultat de la primitive. On la documente par :doc. La macro-chaîne finale #{(($A) * ($B))}# décrit comment générer le code C associé à chaque utilisation de cette primitive et contient les deux variables a et b.

Construction Syntaxe Exemple Note
litéraux entiers comme en C -2 le truc entier -2 (ce n'est pas une valeur !)
litéraux chaînes comme en C "a\tb" un truc chaîne à 3 caractères dont une tabulation
(ce n'est pas une valeur !)
symboles quotés (quote symbole) ou simplement 'symbole (quote if) c'est-à-dire 'if la valeur symbolique if
un objet Melt de CLASS_SYMBOL
entier quotés 'nombre '2 la valeur 2 de DISCR_CONSTANT_INTEGER
chaînes quotées 'chaîne ' "Melt" la valeur chaîne de 4 caractères de DISCR_STRING
conditions simples (if test alors sinon) (if (>i x 0) x 1) C'est une expression qui a un résultat.
conditions successives (cond
  conditions ... )
(cond    ((<i x 10) (f1 u x))    ((<i x 20) (f2 u x))    (:else (f3 u x)))
appelle f1 si x vaut 5,
f2 s'il vaut 15,
et f3 s'il vaut 100.
Les conditions comportent un test et des expressions.
Chaque condition est évaluée en séquence, jusqu'à un test vrai.
La condition finale est une branche sinon quand son test est :else.
Le résultat est celui de la dernière expression de la condition vraie, ou sinon de la condition :else finale.
opération primitive ( primitive arguments ...) (+i 2 x) où la variable x est liée à un truc entier Tous les arguments sont préalablement évalués dans l'ordre où ils apparaissent. Leur type et leur nombre sont prescrits par la primitive. Le résultat a un type figé (truc ou valeur), selon la primitive.
appel de fonction ( fonction arguments ...) (f () 1) ou (g) Tous les arguments sont préalablement évalués. La fonction peut être elle-même donnée par une expression complexe. Le premier argument, s'il y en a un, doit être une valeur. La signature d'une fonction, donnée par ses arguments formels, est figée. Les arguments excédentaires ou manquants ou de mauvais types sont effacés.
itération ( itérateur (arguments ...) (variables-locales ...) corps ... ) voir plus bas Itérer, selon l'itérateur indiqué, en donnant initialement les arguments... indiqués. Chaque itération verra des variables-locales liées différemment dans le corps de la boucle d'iteration.
envoi de message ( selecteur receveur arguments ...) (sel (f x 1) "ab") Le receveur est évalué en une valeur (pas un truc). Tous les arguments sont préalablement évalués. Le discriminant du receveur détermine quelle méthode associée au selecteur est invoquée.
affectation (setq variable expression) (setq x i) le résultat d'une affectation est la nouvelle valeur de la variable affectée.
Les affectations servent rarement !
évaluation en séquence (progn expressions...) (+i (progn (f) 1) 2) vaut 3 après avoir appellé f sans arguments. Evalue en séquence une suite d'expressions pour leurs effets de bord. Le résultat de la dernière expression est renvoyé. Ressemble à l'opérateur , de C.
liaisons locales (let ( liaisons ...)
  corps ...)
(let ( (:long i 2)     (:long j (+i i 3)) )   (setq x i) (f2 'x j)) Définit des variables locales par les liaisons indiquées et évalue les sous-expressions du corps en séquence avec ces définitions locales. Les variables sont locales, donc indéfinies à l'extérieur du let.
création d'instance (instance classe :champ1 valeur1 ...) (instance class_container :content_value 'a) Crée dynamiquement une valeur objet, instance d'une classe donnée, et remplit ses champs (avec les valeurs indiquées). L'accès et la modification des champs d'un objet se font par get_field et put_fields non traités ici.
définition d'instance nommée (definstance nom classe :champ1 valeur1 ...) Voir ci-dessous l'exemple du mode test_fopen Crée « statiquement » une instance nommée, d'une classe donnée, et remplit ses champs (avec les valeurs indiquées)
définition de fonction (defun nom ( formels ) corps... ) Voir les exemples plus bas, dont say-hello-if et test_fopen_exec Définit une fonction par ses arguments formels et son corps. Le premier argument formel, s'il y en a un, doit nommer une valeur. Le corps de la fonction est une suite d'expressions évaluées en séquence, dont la dernière donne le résultat principal (une valeur) de cette fonction.
renvoi de résultat(s) (return résultats...) (return x) Renvoie un résultat primaire (une valeur, Nil par défaut) et éventuellement d'autres résultats secondaires. Il faudrait utiliser multicall (non traité ici) pour capturer les résultats secondaires.
inclusion de morceau de code C (code_chunk symbole-d'état macro-chaîne ) (code_chunk foo #{$FOO#_lab: $N++;   if ($N * $N < 100)     goto $FOO#_lab;}#) Le code C généré par MELT contient le morceau de code donné par la macro-chaîne, où le symbole-d'état est remplacé par un identifiant unique, et où les variables Melt (prefixées par $) sont correctement substituées. Cette expression Melt n'a pas de résultat.
filtrage (pattern-matching) (match expression filtrage ... )
Chaque filtrage commence par un motif (pattern).
voir plus bas L'expression à filtrer produit une donnée, qui est filtrée par les motifs de chaque cas de filtrage. Le premier motif filtrant voit ses sous-expressions évaluées, en y liant les variables de filtrage. Le résultat du match est donné par la dernière sous-expression du cas filtrant.
filtre joker (motif passe-tout) ?_ voir exemples Ce filtre accepte toute donnée. Il sert dans un cas de filtrage fourre-tout, généralement le cas final d'un match.
variable de filtre (motif) ?nom ?x Si la variable (ici x) a déjà été filtrante, teste que la variable vaut la donnée préalablement filtrée, sinon lie la variable à la donnée en cours de filtrage.
motif (ou filtre) composite ?(filtre arguments ...
  sous-filtres ...)
?(tree_function_decl   ?(cstring_same "fopen") ?_) Le motif teste selon le filtre indiqué avec les arguments ..., les données extraites sont passées aux sous-filtres.

Tableau de quelques constructions syntaxiques en MELT (il en existe d’autres)

3. Écriture concrète d'un module en Melt

L'intérêt de MELT réside dans sa proximité avec Gcc, il va permettre de travailler facilement dans ses représentations internes et ses types. Il permet une certaine abstraction, mais nécessite tout de même que l'utilisateur comprenne les principaux ressorts de Gcc.

3.1 Les passes de Gcc

Les passes correspondent aux traitements successifs qui sont réalisés sur le code, il peut s'agir de transformation du code en une nouvelle représentation (GENERIC par exemple) ou de réaliser des optimisations sur le code. Il existe un grand nombre d'optimisations et de ce fait Gcc comprend un nombre impressionnant de passes.

Pour donner quelques exemples d'optimisations, elles peuvent être simples, comme supprimer le code mort, ou plus complexe à l'image de l'option mudflap, qui va ajouter des exceptions lors d'opérations délicates sur des pointeurs, pour protéger contre les overflows et autres opérations dangereuses.

3.1.1 Visualisation concrète dans Gcc

Gcc permet d'obtenir un fichier de dump pour chaque passe visualisée, on peut ainsi voir le résultat du code après transformation du code dans une forme ou une autre. Pour cela, on utilise la commande suivante :

gcc -fdump-tree-all monfichier.c

Cette option permet de voir chaque passe exécutée au niveau middle-end. Selon le niveau d'optimisation auquel on travaille (-O0 pas d'optimisation particulière, -O1 quelques optimisations jusqu'à -O3 (optimisations importantes avec un travail long du compilateur)), on aura un nombre plus ou moins important de fichiers. Si l'on veut ne voir que le fichier ssa, on peut utiliser :

gcc -fdump-tree-ssa monfichier.c

Il est également intéressant de regarder le fichier .vcg, il contient un format texte permettant de décrire le graphe de contrôle de la fonction. Basiquement, le graphe de contrôle permet de voir les différents blocs basiques (ensemble d'instructions séquentielles, c'est-à-dire sans conditions ni boucles) et les liens entre eux.

Grâce au logiciel vcgview (http://code.google.com/p/vcgviewer), on peut visualiser le graphe de différentes manières et sauvegarder l'image au format png.

Figure 2 : Un exemple de graphe de
contrôle

3.1.2 Le désordre c'est l'ordre ?

Il est temps de soulever un point important sous Gcc : on ne sait pas à l'avance quelles passes vont s'exécuter et dans quel ordre cela se fera. On pourra donc lancer le programme avec les options de dumps pour voir les passes exécutées. Cependant, c'est peu satisfaisant, car selon les optimisations passées au code, ces passes peuvent changer. Attention encore, le format des fichiers dumpés est bien « nom_fichier_compilé.c.XXXt.ext » avec XXX un nombre et ext une extension. Cependant, le XXX correspond à un numéro statique associé à la passe, et ne donne pas d'indication concernant l'ordre d'apparition de celle-ci.

3.2 Les principales représentations

Comme nous l'avons vu, il existe de nombreuses représentations du code, nous allons détailler les principales au niveau middle-end :

- GENERIC : On la considérera comme la représentation la plus basique sur laquelle on pourra travailler, il s'agit d'un arbre syntaxique abstrait (en anglais AST, Abstract Syntax Tree). Il existe plus de 180 types de trees, dont le détail est donné dans le fichier gcc/tree.def. À noter également que cette représentation est générique quel que soit le langage source compilé.

/* C unary `*’ or Pascal `^’. One
operand, an expression for a pointer. */
DEFTREECODE (INDIRECT_REF, “indirect_
ref”, tcc_reference, 1)

le code représentant l’opérateur d’indirection dans le fichier gcc/tree.def

- GIMPLE : Les déclarations GIMPLE sont des instances de type GENERIC avec davantage de restrictions, en particulier on parle de three-address code car les informations sont stockées sous la forme (opérateur, opérande1, opérande2). Un gimple représentera ainsi une instruction de notre programme. Le nombre de types est restreint à environ 35. Les différents types de GIMPLES peuvent être trouvés dans le fichier gcc/gimple.def. Cette représentation (définie dans gcc/gimple.h) est tellement centrale et tellement critique dans Gcc qu'il est peu probable de l'imaginer changer. En effet, ajouter un unique champ au type GIMPLE aurait une forte implication sur les performances et la mémoire consommée par Gcc.

/* GIMPLE_CALL <FN, LHS, ARG1, ..., ARGN[, CHAIN]> represents function
calls.
FN is the callee. It must be accepted by is_gimple_call_addr.
LHS is the operand where the return value from FN is stored. It may
be NULL.
ARG1 ... ARGN are the arguments. They must all be accepted by
is_gimple_operand.
CHAIN is the optional static chain link for nested functions. */
DEFGSCODE(GIMPLE_CALL, “gimple_call”, GSS_CALL)

Le code représentant l’appel à une fonction dans gcc/gimple.def

- GIMPLE SSA : Très proche du GIMPLE, avec une particularité : une variable ne peut être associée qu'une et une seule fois. Pour cela, les variables sont divisées en « versions », les variables sont alors composées du nom original et d'une extension précisant la version.

- RTL : Register Transfer Language. Cette représentation bas niveau est utilisée dans la dernière partie du compilateur, qui génère le code assembleur. Nous ne traiterons pas de cette partie.

3.3 Utiliser MELT

3.3.1 Installer MELT

MELT est disponible sur http://gcc-melt.org. Il peut être installé sous deux formes : soit en tant que branche de Gcc, soit en tant que greffon à Gcc. Installer la branche nécessite de recompiler l'ensemble de GCC et s'avère parfois périlleux, cela permet de travailler sur la dernière version de MELT. Il est conseillé de commencer avec la version greffon, qui est plus stable et simple à utiliser. Cela nécessite de disposer d'un Gcc en version 4.6 ou supérieur. La liste des options à passer au compilateur lors de l'utilisation de MELT varie légèrement selon la version, l'article utilise le format de la version greffon, renseignez-vous si vous utilisez la branche. Un dernier point, Mandriva via le travail d'Alexandre Lissy a suivi de près MELT et dispose de ses propres paquets pour installer MELT de façon simple dans la Mandriva 2011. Vous pouvez donc choisir cette solution.

3.3.2 Un simple « hello world » avec Melt

Il est grand temps d'écrire son premier fichier Melt. Celui-ci ne sera pas d'une grande utilité, il permettra principalement de comprendre comment l'on insère du code Melt dans Gcc. Le fichier permettra d'afficher un « hello world » lors de la compilation.

;;-*-mode:Lisp;-*-
;;file hello.melt
;; say hello world when this MELT module is loaded
;; define the say-hello-if function.
(defun say-hello-if (p :cstring msg)
(if p
(code_chunk hellochunk
#{/*$hellochunk#_here*/ printf(“hello %s\n”, $msg);}#
)
)
)
;; call the function with the symbol YES as first argument
;; ... and the C string stuff “world” as the second one
(say-hello-if ‘yes "world")

Vous avez certainement compris qu'en Melt, le symbole; correspond à un début de commentaire. Vous retrouvez également la syntaxe Lisp vue précédemment. Ici, on définit une fonction say-hello-if à l'aide du mot-clé defun. Celle-ci prend 2 arguments (p et msg). p correspond à une value, donc une donnée propre à MELT, alors que msg est un truc, ici une chaîne de caractères C. Nous avons déjà vu le code_chunk permettant d'écrire directement du C. La dernière ligne représente un classique appel de fonction.

3.3.3 Compiler un module

L'étape suivante consiste à pouvoir compiler sous la forme d'une bibliothèque .so le module que l'on a créé. On va utiliser pour cela la ligne de code suivante :

# gcc -fplugin=melt -fplugin-arg-melt-mode=translatetoplugin -fpluginarg-
melt-arg=hello.melt -c empty.c

MELT propose différents modes de fonctionnement. translatetomodule permet de convertir le fichier hello.melt en un fichier hello.c, à son tour compilé en une bibliothèque .so. On retrouve alors ce fichier dans le répertoire courant. Il est nécessaire de passer un fichier empty.c à compiler, sans quoi le compilateur renvoie une erreur. N'importe quel fichier (y compris un fichier vide) suffira et ne sera pas modifié.

Il est possible de voir le fichier C généré en utilisant translatefile plutôt que translatetomodule :

# gcc -fplugin=melt -fplugin-arg-melt-mode=translatefile -fplugin-argmelt-
arg=hello.melt -fplugin-arg-melt-output=helloMELT.c -c empty.c

Désormais, on va pouvoir effectivement tester le module sur un fichier C de notre choix. Le mode noop ne fait rien d'autre que de laisser charger les bibliothèques et lancer leur exécution. -fmelt-init permet de déterminer le fichier .so à utiliser, -fmelt-module-path détermine dans quel répertoire se trouve le module.

# gcc -fplugin=melt -fplugin-arg-melt-mode=noop -fplugin-arg-meltinit=@@:
hello -fplugin-arg-melt-module-path=. -c test.c

Si tout s'est bien déroulé, vous devriez voir s'afficher dans votre terminal le fameux ''hello world''.

Il existe d'autres modes MELT, que je vous invite à explorer. Pour connaître leur liste et leurs fonctions, il suffit de taper :

# gcc -fplugin=melt -fplugin-arg-melt-mode=help -c test.c

3.3.4 Une véritable passe

Notre hello world était amusant, mais pour autant, il n'a pas travaillé sur le code C que l'on cherche à compiler. Il est temps d'écrire une passe qui soit capable d'étudier le code du fichier passé au compilateur. Ce sera l'occasion de découvrir les dernières fonctionnalités de MELT.

Voici un exemple permettant de comprendre le genre de module qu'il est possible d'écrire. Vous connaissez certainement la fonction C fopen() qui permet d'ouvrir un fichier. Elle retourne un pointeur sur un FILE. C'est évidemment une bonne pratique que de tester que ce pointeur n'est pas NULL plutôt que d'avoir de mauvaises surprises par la suite. Nous allons donc voir les différentes étapes pour écrire une passe vérifiant (de façon naïve, fonctionnant dans le cas courant) que la fonction est bien testée.

3.3.4.1 Définir sa passe

;;declare the pass
(defun test_fopen_docmd (cmd moduldata)
(let ( (test_fopen
(instance class_gcc_gimple_pass
:named_name ‘”melt_test_fopen”
:gccpass_gate test_fopen_gate
:gccpass_exec test_fopen_exec
:gccpass_data (make_maptree discr_map_trees 100000)
:gccpass_properties_required ()
)
))
;;try to add it after the SSA pass (try after phiopt if problem)
(install_melt_gcc_pass test_fopen “after” “ssa” 0)
(debug_msg test_fopen “test_fopen_mode installed test_fopen”)
;; return the pass to accept the mode
(return test_fopen)
))

Cette fonction permet de déclarer la passe et de définir ses attributs. On remarque ici que l'on travaille sur une passe se faisant au niveau GIMPLE (on instancie un objet de la classe class_gcc_gimple_pass). On donne un nom à notre passe, melt_test_fopen (ce nom sera utilisé dans les fichiers de dump), on explicite une fonction gate, cette fonction servira à expliquer sous quelles conditions on exécute la passe ou pas (en pratique, ça peut être selon que des options d'optimisation soient appelées ou non, cela peut également être par rapport à des informations sur le code). gccpass_exec définit la fonction qui réalisera le traitement de la passe. gccpass_data permet de stocker des éléments propres à la passe. En général, on va stocker dans gccpass_data l'arbre de la fonction.

Parfois, une passe peut nécessiter certaines propriétés pour s'exécuter, ici on ne s'en occupera pas.

La dernière partie concerne la position à laquelle on insère la passe dans Gcc. Comme nous l'avons vu, il est difficile de connaître l'ordre d'exécution des passes. Souvent, on a un ordre d'idée de la position à laquelle on veut insérer sa passe, cela peut être au niveau de la représentation SSA comme ici. Ensuite, il vaut mieux tester que la passe dispose des bonnes informations pour s'exécuter et qu'il n'y a pas d'incompatibilités avec les autres passes.

3.3.4.2 Définir un mode

(definstance test_fopen
class_melt_mode
:named_name ‘”test_fopen”
:meltmode_help ‘”monitor that after each call to fopen, there is a
test on the returned value”
:meltmode_fun test_fopen_docmd
)
(install_melt_mode test_fopen)

Nous avons déjà vu un certain nombre de modes (en particulier translatetomodule), dans le cas général, l'utilisateur va vouloir ajouter ses propres modes pour lancer ses passes particulières. Pour ajouter un mode, il suffit de déclarer une instance de la classe class_melt_mode Elle comprend un nom (sous la forme d'une value), une aide et une fonction principale, ici test_fopen_docmd, que nous venons d'analyser et qui est appelée au lancement du mode. La fonction install_melt_mode permet d'installer effectivement le mode.

3.3.4.3 Fonction Gate

On doit définir la fonction gate que nous avons utilisée dans test_fopen_docmd. Si cette fonction retourne NULL, on ne passera pas plus loin dans la passe, si cette fonction retourne autre chose, on exécute la passe. La fonction présentée ici est triviale et retourne toujours quelque chose de non NULL.

(defun test_fopen_gate(pass)
(debugtree “Entering test_fopen_gate “ pass)
pass
)

3.3.4.4 Déboguer dans Melt

L'usage de la fonction debugtree permet de mettre en valeur la façon dont on peut déboguer du code Melt et comprendre la structure des données dans Gcc. En effet, si lors de la compilation, on passe l'argument -fmelt-debug, on aura tout un ensemble d'informations de debug qui sortiront sur la sortie d'erreur. Ce flux est important et certaines informations ne sont pas utiles aux simples utilisateurs, mais cela permet tout de même souvent de comprendre une erreur et d'observer la structure des arbres et gimples.

Par exemple, on trouvera comme information :

@! debugtree test_fopen_gate cfundecl @0x41a93580 /function_decl
<function_decl 0x41a93580 hello
... //ensemble d’informations concernant la fonction hello
(argument, retour....)
@! debugtree test_fopen_gate cfundecl @0x41a93600 /function_decl
<function_decl 0x41a93600 main
... //ensemble d’informations concernant la fonction main

Ici, hello et main correspondent à deux fonctions du programme que l'on compile. On constate donc que la passe est appelée successivement pour chaque fonction que l'on compile. Le détail n'est pas donné, mais l'on peut obtenir des informations sur la fonction, son type retourné, ses arguments.

3.3.4.5 Fonction exec

On va maintenant pouvoir s'attaquer au cœur de notre passe, la fonction exec qui correspond à l'exécution de la passe.

;; start pass: only print some debug message, check cfun and call
;; detect_untested_fopen
(defun test_fopen_exec (pass)
(informsg_plain “testing fopen with melt”)
(debug_msg pass “test_fopen_pass_exec pass at start”)
(debugtree “test_fopen_exec start cfundecl” (cfun_decl))
;; gimple ssa passes have a cfg..
(detect_untested_fopen)
(debug_msg pass “test_fopen_pass at end”)
)

cfun_decl est une primitive (traduite en une variable C) donnant la fonction courante inspectée par la passe. On vérifie ici à l'aide d'information de debug que l'on entre bien dans la passe et que cfun_decl est bien présent. Le gros du travail est laissé à la fonction detect_untested_fopen. Pour la comprendre, nous avons encore besoin de deux concepts de Melt : les itérateurs et le pattern matching.

3.3.4.6 Les itérateurs

Melt reprend le concept des itérateurs du C++ (ou du Java d'ailleurs) et fournit en particulier un ensemble d'itérateurs sur les structures classiques de Gcc. On trouve ainsi des itérateurs sur les blocs d'instructions, sur les gimples ou encore sur des maps d'objets. Ces itérateurs sont définis dans les sources de MELT (répertoire gcc/melt) via l'opérateur defciterator, ils commencent généralement par un foreach ou each. La fonction detect_untested_fopen utilise each_bb_current_fun qui permet d'itérer sur l'ensemble des blocs basiques de la fonction. L'élément courant dans l'itération est bb. Elle utilise ensuite eachgimple_in_basicblock pour itérer sur chacun des gimples de bb.

;;pass through each gimple and detect if there is an fopen
;;if there is one, it search for a test
;;the var state is used to know if there was an fopen in the precedent
gimple
;;state=:true if there was one
;;state= () null in other way
(defun detect_untested_fopen ()
(let ((:tree lhs_fopen (null_tree))
(state ())
)
(each_bb_current_fun
()
(:basic_block bb)
(eachgimple_in_basicblock
(bb)
(:gimple g)
(if state;;if previous gimple was an fopen
(progn
(if (==t lhs_fopen (tree_content
(detect_cond_with_null
(make_gimple discr_gimple g))))
;if
(setq state ())
;else
(progn
(warning_at_gimple g “fopen not followed by a test on
his returned pointer”)
(setq state ())
)
)
)
;;else
(progn
(setq lhs_fopen (tree_content
(detect_fopen (make_gimple discr_gimple g))))
(if lhs_fopen
(setq state :true)
)
)
)
))
)
)

3.3.4.7 Le pattern matching(filtrage par motif)

Nous avons gardé le meilleur pour la fin, c'est en effet une des fonctionnalités les plus importantes de MELT. Elle peut ressembler aux expressions régulières type posix, sauf qu'ici on ne travaille pas sur des textes, mais bien sur les gimples qui ont une structure de données plus complexe (ou d'autres structures en arbre de Gcc). Le pattern matching est effectué via l'expression match, il faut avant tout préciser l'objet que l'on souhaite analyser (ici il s'agit de g, notre gimple), ensuite on va placer successivement un ensemble de patterns (filtres). Chacun de ces filtres va d'abord lancer un test sur l'objet matché afin de vérifier certaines caractéristiques, et si le test réussit, on va alors instancier un ensemble de variables. Un pattern commence toujours par le symbole ?.

Prenons le premier exemple de matcher : nous cherchons à matcher les appels à la fonction fopen qui prend deux arguments, on a donc une instruction de la forme :

//var est un pointeur sur un FILE
//chemin est une chaine de caractères indiquant le chemin du
fichier
//mode est une chaine de caractères indiquant le type d’ouverture
var=fopen(chemin, mode);

Cette expression est matchée par la fonction detect_fopen suivante :

;;detect fopen by using a match, return the lhs value
(defun detect_fopen (g)
(match (gimple_content g)
(
?(gimple_call_2 ?lhs
?(tree_function_decl
?(cstring_same “fopen”)
?_)
?arg1
?arg2
)
(progn
(debugtree “the lhs tree” lhs)
(return (make_tree discr_tree lhs))
)
)
(
?_((return (make_tree discr_tree (null_tree))))
)
)
)

Le matcher gimple_call_2 signifie que l'on va chercher un appel à une fonction à 2 arguments (on aurait pu utiliser un matcher qui ne s'occupe pas du nombre d'arguments, mais préciser le nombre d'arguments permet de récupérer facilement les variables à instancier si le test réussit). ?lhs signifie que l'on a un matcher sur la partie gauche de l'expression (ici, on ne précise rien de plus, ne posant pas de condition). Par contre, concernant l'appel de fonction lui-même (callfndcl), on va demander à ce que la déclaration de la fonction (tree_function_decl) vaille la chaîne "fopen". ?arg1 permet de récupérer le premier argument de la fonction dans une variable arg1, de même pour ?arg2 avec le second argument. Nous ne nous servons pas ici de ces arguments, par contre on renvoie lhs, nous devrons en effet, par la suite, vérifier qu'il n'est pas NULL. Le deuxième pattern (?_) est le pattern joker, il match toujours. Il permet ici de renvoyer un null_tree si l'on n'a pas matché d'appel à fopen.

De la même façon, nous écrirons une fonction detect_cond_with_null permettant de détecter que le gimple suivant représente bien une condition valide. Il existe un ensemble de matchers permettant de détecter les différents types de conditions (par exemple gimple_cond_equal ou gimple_cond_greater). Il faut également vérifier que le tree utilisé dans la condition est bien le même que celui représentant le résultat de l'appel à la fonction fopen (ce que l'on fait dans detect_untested_fopen à l'aide de l'opérateur ==t).

3.3.5 Testons notre module

Une fois le module écrit, il ne vous reste plus qu'à le tester. Écrivez un nouveau fichier C simple utilisant fopen (en omettant de tester le résultat de l'appel), par exemple le suivant :

#include <stdio.h>
int main(){
FILE * file;
file= fopen(“/root/test_fopen_cfile.c”, “r+”);
return 0;
}

Compilons le module melt :

# gcc -fplugin=melt -fplugin-arg-melt-mode=translatetoplugin -fpluginarg-
melt-arg=detect_fopen.melt -c empty.c

Compilons le fichier C, tout en appliquant notre module :

# gcc -fplugin=melt -fplugin-arg-melt-mode=translatetoplugin -fpluginarg-
melt-arg=detect_fopen.melt test_fopen.c

Si tout s'est bien passé, nous devrions voir l'avertissement suivant :

test fopen.c:6:5: warning: Melt Warning[#216]: fopen not followed by a
test on his returned pointer

Libre à vous d'étendre le module à des cas plus complexes et de le tester sur de véritables programmes.

3.4 pour finir

Cet exemple devrait vous donner des idées d'utilisations possibles de MELT. Ici, l'exemple est simple et incomplet, mais on peut imaginer des programmes plus complexes : en particulier en travaillant sur les différents appels de fonctions. Cela peut être un moyen d'ajouter un ensemble de diagnostiques ou de métriques. MELT est toujours en évolution, pour l'instant il est encore difficile de l'utiliser pour réaliser des optimisations (modifications des gimples ou autres représentations de Gcc), mais on peut imaginer l'étendre pour cela. Vous pouvez également trouver un exemple de module écrit en MELT permettant de réaliser des tests proches de celui présenté ici, mais de façon plus complète et facilement paramétrable par l'utilisateur : talpo.pvittet.com.

Le site gcc-melt.org contient aussi des documents (souvent en anglais) décrivant MELT avec plus de détails. Il existe aussi un groupe de discussion gcc-melt (en anglais) sur GoogleGroups.