[PDF] CONCEPTION ET IMPLANTATION DUN

View - Download CONCEPTION ET IMPLANTATION DUN

Previous PDF

Next PDF

JEAN-FRANÇOIS RODRIGUE

CONCEPTION ET IMPLANTATION D'UN

COMPILATEUR JAVA OPTIMISANT

Mémoire

présenté

à la Faculté des études supérieures

de l'université Laval pour l'obtention du grade de maître ès sciences (MSc.)

Département d'informatique

FACULTÉ DES SCIENCES ET DE GÉNIE

UMVERSITÉ LAVAL

AVRIL 2000

National Liirary Bibliothèque nationale

du Canada

Acquisitions and Acquisitions et

BibSogiaphic SeMces services bibliographiques

395 Wdirngtcm Street 395, rue Wellington

Ottawa ON KtAON4 OitawaON KiAON4

canada Canada The author bas granted a non- L'auteur a accordé une licence non exclusive licence allowing the exclusive permettant à la National Li'brary of Canada to Bibliothèque nationale du Canada de reproduce, loan, distribute or sell reproduire, prêter, distri'buer ou copies of this thesis in rnicroform, vendre des copies de cette thèse sous paper or electronic formats. la fome de rnicrofiche/nlm, de reproduction sur papier ou sur format

électronique.

The author retains ownership of the L'auteur conserve la propriété du copyright in this thesis. Neither the droit d'auteur qui protège cette thèse. thesis nor substantial extracts from it Ni la thèse ni des extraits substantiels may be printed or otherwise de celle4 ne doivent être imprimés reproduced without the author's ou autrement reproduits sans son permission. autorisation.

Résumé

Aujourd'hui, Ies compilateurs modernes utilisent plusieurs techniques d'optimisation afh d'améliorer les performances des programmes qui Iui sont soumis. Mais iI y a encore un grand nombre de voies possibles à expIorer en ce qui concerne les optimisations, surtout pour les langages orientés-objets tek que Java et C*. Nous présentons dans ce mémoire I'impIantation d'un compilateur Java, qui senrira de base d'étude et d'implantation de techniques d'optimisation, ainsi qu'une nouvelle approche pour optimiser la compiIation de ce langage. JeamFrançois Rodrigue Nadia Tawbi Mourad Debbabi Étudiant Directrice de recherche Co-directeur de recherche

Avant-propos

Ce projet de maîtrise a demandé beaucoup de travail et de volonté de ma part. Après tant d'efforts, je suis enfin parvenu ê terme. le n'aurais pas pu terminer ce projet sans I'aide et le soutien mord de plusieurs personnes que je veux remercier. Je veux tout d'abord remercier Mme Nadia Tawbi, ma directrice de recherche. Sans son aide et ses nombreuses remarques coclstructives je n'aurais pas fait un travaiI de cette qualité. Son dévouement envers ses étudiants de recherche est une qualité remarquable. Je ne peux pas oublier la générosité de M. Mourad Debbabi. Sans lui je n'aurais même pas commencé ce projet. I1 a vu bien avant moi tout le potentiel que j'avais pour réaliser ce pro jet. le remercie messieurs EI Hachemi Alikacem et Hamdi Yahyaoui pour leur collaboration et leur persévérance. Je sais que ça n'a pas toujours 4é facile. Je veux remercier aussi mes amies Lise, LiIy et Norafda pour leur soutien mord. Le temps que nous avons passé ensembIe m'a permis de penser à autre chose que Ie travail et les

études,

J'aimefais égaiement remerckrnes parents et mon fière tout simpIement pour être là- J'aÎ enfin terminé le pIus grand projet que j'ai entrepris. Je suis bien content de pouvoir passer à mie autre étape de ma vie, qui sera sûrement pIus paisible.

Table des Matières

Avant-propos eoeoeeeoeeeeeeeeeeme~eemeeemeeeeoeaeeeeeeeeeeeeeoaeoeeeeeoeeeeeeee.eeeee eeeeeeeeeeee 4 w Table des matieres o~~eee~~e~~~e.~~~oe~~~eeee~~~eooo~omoe~~~eooeo~e~eee~e~eoe~~e~oeooeoo~eo ooo~5 Liste des figures ........................................................................ ........ 9 Chapitre 2 Analyse lexicale et syntaxique ................................. 14

2.1 Introduction ......................~.................................................

........................................... 14

2.2 La structure généraie d'un compiIateur .................................................................... 14

2.3 Qu'est-ce que I'anaiyse lexicale? ........................................................................

.......... 16

2.4 Qu'est-ce que l'analyse syntaxiqpe? ......... ... ............................................................ 18

............................................................... 2.5 Un analyseur Iexicd et syntaxique pour Java 20

2.6 La structure de notre compilateur lava ..23

2.7 La structure de I'arbre syntaxique ........................................................................

......... 26

2-8 ConcIusÎon ........................................................................

............................................ 35

3.1 Introduction ........................................................................

........................................... 36

3 3 Qu'est-ce que I'analyse sémanticpe? ........................................................................

.. ..37

33 L'andyse sémantique de notre compiIatem Java ......................................................... 38

3 -4 Impoaaton de cIasses et de modules ........................................................................

.... 38

3.4.1 La Iecture des fichiers . class ........................................................................

.. 39

3-42 La recherche d'un fichier . clâss ................................................................... ..39

3.43 L'bpoaation de classes et de modules ......................................................... 42

................................................... Le changement des noms simples en noms complets 43

............................... Znférence de types ..43

............................................................... 3.6.1 Qu'est-ceque I'inférencedetypes? 44

.......................... 3.62 Description de l'inférence de types pour notre compilateur 45

3.6.3 La variable d'environnement pour notre compilateur Java ........................... 46

.............................................. 3.6.4 Quelques fonctions pour l'mférence de types ..47

3.6.5 L'inférence de types pou. Ies instructions ..................................................... 50

3.6.6 L'inférence de types pour les expressions ..................................................... 60

3.6.7 La recherche d'une méthode ........................................................................

.. 83

3.6.8 La recherche d'un champ ........................................................................

....... 86

3.69 La décomposition des noms ........................................................................

... 87 ............................................ Conclusioo 91

4.1 uitroduction ........................................................................

......................................... ..92 ..... 4.2 La machine virtuelle Java ........ 93

42.1 Introduction ................................................................ 93

....................................................... 4.22 La structure de la machine vktuefle Java 93

42.3 Exécution d'un programme Java ...........................~................................ 95

............................. 41.4 ConcIusion 98 .............. . 4.3 La structure d'un fichier class 98 ............................ 4.3.1 Introduction 98

........................... . ................... 43.2 Le format du fichier class ......................... 98

4.3.3 La table des constantes .~......................................................................

......... 100

43 -4 Les champs ........................................................................

.......................... 102 ....................... 4.3.5 Les méthodes 103

43.6 Le code .................~......................................................

................................. 104 4.3.7 Conclusion ........................................................................ ........................... 105

4.4 Le générateur de code .............. .. .............................~..........................................

......... 106

4.4.1 Introduction ........................................................................

.......................... IO6

4-42 La strrrcttxre ghéraie du génaatem de code ................................................ 106

4.4.3 Lecture, écritme et afnchage d'me structure . cIass ..................................... 107

4.4.4 Création de la tabIe des constantes .............................................................. 108

4.4.5 Fonctions d'aide à Ia génhtion de code ..................................................... 109

4.4.6 La fonction generateByteCode() et Ia varia& d'enviromement ............... 1 12

4.4.7 ConcIusion ........................................................................

........................... 1 15 ................................ 116

4.5.1 Introduction ........................................................................

.......................... 116

.................................................. 4.52 Optimisation des indices et des constantes II7

.............. 4.5.3 Incrétnentation et décrémentation de varïabIes Iocales de type int 119

............................................................ 4.5.4 La préparation pour une assignation 120

4.5.5 Les branchements conditionnels .................................................................. 122

r

4.5.6 L'instruction de selectron ........................................................................

.... 124

4.5.7 D'autres optimisations possibIes ................................................................. 125

...................................................... 4.5.7.1 L'élimination de ceaains goto 126 ................... 4.5.7.2 La concaténation multiple de chaînes de caractères .. 126

4.5.7.3 Une analyse de flot de données simple ........................................ 127

4.5.8 Conclusion ........................................................................

........................... 128

4.6 Conclusion ........................................................................

.......................................... 128 ............. ............. Chapitre 5 Analyse de flot de contrôle ... 129

5.1 Introduction .......~................................................................

......................................... 129

............ 5.2 Étude de l'état de l'art ................................................................... ..... 130

5.3 Représentation du flot de contrôle ................... ... .................................................. 133

5.3.1 Définition d'un graphe do fiot de contr6Ie ................................................... 133

5.32 Dékition d'un graphe de Bot de contrôIe interprocédd ......................... 134

5.3.3 Définition d'un graphe d'appels .................................................................. 134

5.4 Les exceptions en lava .~....................~.................................................

....................... 135

5.4.1 Hierarchie des exceptions ........................................................................

.... 135 ....... 5.4.2 La cause des exceptions 135

5.4.3 Les exceptions en lava ........................................................................

......... 136

54.4 Le traitement des exceptions ........................................................................

137

5.5 Analyse dit flot de contrôle ........................................................................

............... 139

5.5. I Analyse de flot de contrÔIe au niveau mtraprocédd ................................ 139

5.5.2 Analyse de flot de contrôfe au niveau interprocédd ................................ 140

5.521 CaIcul de i'ensembIe des receveurs d'une invocation de méthode

........................................... 140

5-5-22 L'initisilisation d'une classe .......................................................... 143

............ 5.52.3 La propagation des exceptions au niveau hterprocédurai 144

5.6 Raffinement de I'anafyse de flot de contrO1e pin mie andyse de ff ot de données ...... 144

.......................................... 5.7 Conchsion 145

5.7.1 Contn'butions ........................................................................

.................... 145

5.7.2 Perspectives ........................................................................

.......................~. 145 ................... Chapitre 6 Conclusion .... .............................. 146

6.1 Objectifs ........................................................................

.............................................. 146

6.2 Contriiutions ........................................................................

...................................... 146

6.3 Perspectives ..................... ....... .......................................................................

148
Bibliographie ........................................................................ ........ 149 Annexe A Algorithme de construction du graphe de flot de ............................................ contrôle au niveau intraprocédural 151 Annexe B Algorithme de construction du graphe de flot de ....................... contrôle au niveau interprocédural ................... 159 Annexe C Métriques ................................................................... 162 ............. Annexe D Exemple d'exécution du compilateur Java 164

Chapitre 1

Introduction

Depuis les années soixante, la performance des ordinateurs a suivi une progression fiilgurante. Si nous comparons les ordinateurs du début des mées 80 avec ceux d'aujomd'hui, nous réalisons qu'en moyenne, à chaque période d'environ 2 ans, la vitesse et la capacité de mémoire des ordinateurs sont muItipriées par 2. Cette hausse de performance permet de résoudre des problèmes de plus en plus complexes. Eue permet aussi, entre autres, la création de logiciels interactifs avec une présentation graphique de pIus en pIus sophistiquée. La qualité des Iogiciels de nos jours est sowent mesurée autant par ses performances que par ses autres @tés teiIes que sa EabiW, son côté pratique ou sa facilité d'utilisation. Un logiciel qui fait tout ce que l'utilisateur veut, mais dans le même temps que si c'était

fait à Ia main., a de fortes chances d'être rejeté. Amsi, un IogicieI se doit d'être efficace en

terme de rapidité pour être vendu, surtout s'a y a de Ia compétition dans le domaine ciblé.

II y a pIusieurs factenrs B consÎdk pour obtenir mi IogiÜeI rapide et efficace comme produit fial. J'en nomme ici quekpes mis : En généd, pIus un Iangage est de bas niveau, pIus il est possible de générer du code efficace. Par contre, les langages de bas niveau sont diffides à maîtriser et nécessitent plus de code pour effectuer le même traitement que dans un langage de haut niveau,

La conception architecturale du logiciel.

Un logicid rnd conçu au depart sera inefficace, peu importe le choix des autres facteurs. II est important de choisir une structure aussi simple et efncace que possible.

La conception des atgorilhmes.

Même avec le meilleur compilateur et le meiIIeur programmeur, un mauvais algorithme sera inefficace. Par exemple, s'il faut trier des milliers de données, un algorithme qui prend un temps dans l'ordre de n log n tel que Ie tri de WiUiams (&eapsorb>) sera nettement plus efficace qu'un autre qui prend un temps dans l'ordre de n' te1 que le tri par sélection.

La programmation @dente des algorithmes.

Un même algorithme programmé par deux personnes peut être exécuté en des temps considérablement différents. Malheureusement, le programmeur moyen n'a pas le souci d'optimisation. Cependant, cette lacune peut parfois être comblée par les optimisations de haut niveau d'un bon compilateur.

Le choir d'un compiiateur optimisant.

II existe des dizaines de techniques d'optimisation, et les compiIateurs Les plus efficaces utilisent la majorité des techniques les plus connues. Dans ce memoire, nous nous intéressons principalement aux optimisations que peuvent effectuer Ies compiIateurs. Nous avons choisi le langage Java comme pIate-forme d'optimisation pour plusieurs raisons Java est un Iangage orienté-objet et les optimisations concernant ce type de Iangage se prêtent encore a bien des améfiorations; C'est un Iangage moderne en vogue, et de pIus en plus utiIisé;

Le code coq* de Java est portable.

La popdarite de Java est due à sa poaabilité, même à tmvas les réseaux teIs que I'Internet,

et parce que sa syntaxe rappek cek du Iangage C* qui est le langage le pIw utilisé en mfomiatiqne à I'heure achielIe. Java a été conçu par James Goshg chez Sun Microsystems Fof981. C'est un langage onenté objets qui ressemble beaucoup au C++' mais où p1~1sieurs aspects compIexes ou qui portent à f& des erreurs ont ét6 supprimés. Par exemple, Java est fortement typé et ne contient pas de pointeurs. C'est un Iangage relativement de haut niveau puisqu'iI cache

tous les détails de la machine où sera exécuté le code compilé [Gos96]. Le code Java est

compiIé en bytecode. CeIui-ci sera interprété par une machine +elle Java (MVJ). Grâce à sa popdanté, il existe une MVJ pour la phpart des plates-formes actuelles. Au sein de l'équipe LSFM (danguage Semantics and Forma1 Methodm), au département d'informatique de l'université Laval, est né le projet Bon-Java Ce projet consiste à impIanter un compilateur Java afin d'étudier et d'implanter de nouvelles techniques d'optimisatioa. Le compilateur Java est Iui-même implanté en Java pour sa portabfité. 11 peut être exécuté sur n'importe queue machine qui contient une MVJ. M. El Hachemi ALikacem et moi-même avons implanté un analyseur lexical et syntaxique pour Java Celui-ci génère une stnicture intermédiaire par cIasse analysée dans le code

Java Ce document est structuré comme suit: au chapitre 2 je décris la stnicture générde de

notre compilateur, ainsi que la façon dont nous avons impIanté les phases d'analyse

Iexicaie

et syntaxique. Au chapitre 3, je d6m.s l'implantation de la phase d'anaiyse sémantique du compilateur, à savoir I'importation de classes et de modules. le changement des noms simples en noms complets, et I'infhnce ue types qui permet de typer chaque expression d'une structure dgorithme d'expression, et comment j'ai comgé deux algorithmes incorrects définis dans [Gosgq. Cet dgorithme constitue une spécincation algorithmique de la spécincation de [Gos96] sur

Ie caIcuI de types pour Iava

J'amorce Ie chapitre 4 par mie description de Ia machme virtuelle Java et de la structure des fichias cIass. Chaque fichier class représente une classe Java compilée, Je décris ensuite comment j'ai HnpIanté mi gén6rateu-r de code pour notre compilateur, ainsi que queIqpes optimisations que j'ai faites à ce nive= I'indiqne, avant de concIuce le chapitre, cpekpes opb-sations qrà porrrraient être faites pins tacd par un autre membre du projet Bon-Java. Le chapitre 5 sur I'analyse de flot de contrôle, une phase plimordide pour toutes les analyses de flots de données et Ies optimisations qui en découlent Nous apportons une noweile approche qui permet d'améliorer 17anaIyse de flot de contrôle aux niveaux intraprocédural et interprocédumI pour Java, et eue est indépendante de la machine cible. Cette approche a été déveIoppée en coilaboration avec M. Hamdi Yahyaoui, qui fait aussi partie du projet Bon-Java Après me conclusion générale, je décris en annexe les aigorithmes d'analyse de flot de contrôle aux niveaux intraprocédurai et interprocédurai.

Chapitre 2

Analyse lexicale et syntaxique

2.1 Introduction

Dans ce chapitre nous allons voir ce que sont l'analyse lexicale et I'andyse syntaxique. Au prédable. nous allons définir brièvement les différentes phases du processus de compilation. Nous verrons comment nous avons implanté un analyseur lexical ainsi qu'un anaIyseur syntaxique dans le cadre d'un projet de développement d'un compilateur Java

optimisant. Nous définirons Ia structure de l'arbre syntaxique, aussi appelée représentation

intermédiaire, qui est généré par I'analyseur syntaxique, et comment il peut être utilisé à

des fins d'optimisation.

2.2 La structure générale d'un compiiateur

Le processus de compilation est généraiexnent composé d'un ensemble de phases qui transforment un programme source d'mie représentation en une autre. La figure 2.1 représente Ies différentes composantes d'un compiIateur typicpe. L'analyseur IexicaI iit Ie fichier source et le décompose en jetons p7iI transmet it PanaIyseur syntaxiqne. Ce dernier pmgramme snit Ies règles syntsucicpes définies par Ia grammaire du langage utilisé. EI génére en méme temps un arbre syntaxique qui représente Ie programme source en une forme intermédiaire. Dans un troisième temps, le compilateur vérifie que les règIes sémantiqes du langage sont respectées. Ces trois premières phases constituent l'analyse du programme source. Par Ia suite, dans une phase optionnelIe, le code peut être optimisé dans Ie but d'être exécuté plus rapidement etfou d'utiliser Ie moins d'espace mémoire possible. En dernia Iieu, Ie code sera gent56 dans un langage cibIe qui pourra être soit exécutable, soit interprétable par un autre programme. programme source

Compilateur

1 ma1yseur IexicaI

1 analyseur syntaxique

1 anaiyseur sémantique gestionnaire [L1-] ci*murs 1 optimiseur de code Cr

1 génératarde code

programme cibIe messages d'erreur

Figure 2.1 Composantes d'un compiIateur typique

Bien entendu, les cinq phases décrites précédemment ne définissent pas tous les

compilateurs. Certaines phases peuvent aussi être enchevêtrées ou être exécutées en même

temps. Plusieurs compiIateurs commerciaux tentent de limiter le nombre de passes effectuées sm le code afin de compiler plus rapidement les programmes sources. Dans notre compiIateur lava, Ies analyses 1exical.e et syntaxique sont faites en même temps. CeIa de l'andyse syntaxique, et l'autre parti dans me phase séparée appelée v~can'on des typez Présentement, Ie compiIateur n'a pas de phase expIicite d'optimisation de code. II contient cependant cpelques optimisations smipIes fgites Iors de la vénncation du typage, et d'autres sont faites lors de la génération de code. Puisque I'im des bats de notre projet phases d'optimisation seront intégrées UItQiemement au compiIatenr. Lors des phases du processus de compiIation, des erreurs peuvent survenir. Dans ce cas, au

Iieu de générer un programme cible, un ou pIusieurs messages d'erreurs sont générés par le

compilateur. La gestion des erreurs est un processus complexe lorsque nous voulons détecter pIus d'une erreur. Ii faut déterminer les actions à entreprendre afin de pouvoir conhuer

I'anaiyse

du programme dans un état acceptable. Étant dom6 que notre compilateur Java va servir surtout dans le but d'expérimenter des techniques d'optimisation, nous avons omis de fee un gestiomake d'erreurs complexe. Lorsqu'une erreur survient, un message d'erreur est fiché et le processus de compilation est arrêté- De plus, certaines vérifications sémantiques ne sont pas effectuées; notre compilateur va accepter des programmes comportant ces types d'erreurs sémantiques. Dans ce cas, le code

généré peut ne pas passer à l'exécution. La plupart de ces erreurs non vérifiées sont

vérifiées par la machine virtuelle Java qui interprète le code généré. Nous supposons que

Ies programmes sources en entrée sont corrects. Le code généré par notre compilateur pour

un programme correct en entrée sera correct lui aussi et passera les étapes de vérification de la machine virtuelle Java,

2.3 Qu'est-ce que l'analyse lexicale?

Comme nous L'avons vu auparavant, L'analyse lexicale est la première phase du processus

de compiIation. Sa tâche consiste à Lire Ie programme source, à le décomposer en unités

lexiedes aussi appeféesjetom, et à les transmettre à I'analyseur syntaxique. En générai, les types de jetons pour un langage donné sont les suivant:

Les mots dés;

Les chafnes de caractéres;

Les syrnboLes et groupes de symbdes;

Les nombres;

Et les identificateurs,

Le tabIeau ci-dessous ilrustre des exemples d'unités Iemcales. Le langage Java est constitué de plusieurs types de jetons:

Types de jetons

Mots clés

Chaîne de caractères

Symboles

Les opérateurs';

Les chaînes de caractères;

Deux types de nombres entiers et deux types de nombres réels;

Quelques symboles;

Les identificateurs.

Exemples

We, do. fI oat, if

"analyse lexicale" (, 1. +. +-, >, L 1 Parmi Ies mots clés de lava, il y en a un qui n'est pas accepté par sa grammaire: le goto.

Pour connaître la Liste exhaustive des unités IexicaIes acceptées par Java, référez-vous au

chapitre

3 de [Gos96].

Les jetons sont généralement constitués d'au moins deux types d'information: un numéro qui permet d'identifier soit son type, soit son type de symbole, d'opérateur ou de mot dé, etquotesdbs_dbs25.pdfusesText_31

[PDF] chaîne de financement – outils fonds propres

[PDF] Chaine de puissance

[PDF] Chaine de Sécurité MICRO-SESAME - Anciens Et Réunions

[PDF] Chaîne de solidarité des classes de 4°. Jeudi 15 décembre

[PDF] Chaîne des Aravis

[PDF] Chaine Dinner Invitation Reflexions June 2010 - Anciens Et Réunions

[PDF] chaine du froid - Business France

[PDF] Chaîne du froid sécurité alimentaire et développement _note - Généalogie

[PDF] Chaine d`énergie

[PDF] CHAÎNE D`ENERGIE ET D`INFORMATION iRobot Roomba I - Anciens Et Réunions

[PDF] chaîne d`étalonnage

[PDF] Chaîne d`information Chaîne d`énergie

[PDF] Chaîne d`information et chaîne d`énergie

[PDF] chaine eclipse

[PDF] chaine elisa sirio - Support Technique