Cours intégration d’optimisations globales en compilation séparée des langages à objets, tutoriel & guide de travaux pratiques en pdf.

Compilation globale et séparée des langages à objets

La question du caractère global ou séparé de la compilation concerne a priori tous les paradigmes de programmation, mais le polymorphisme des langages à objets rend le problème crucial. Le principe même de l’envoi de message (ou liaison tardive) ne permet pas de savoir, dès la compilation, quelle méthode sera effectivement appelée. Le problème est à peu près le même pour les attributs mais il s’agit alors de leur optimisations en compilation séparée 63 localisation dans la structure de données de l’objet. Enfin, malgré le principe de typage fort, il est souvent nécessaire de savoir si un objet est bien instance d’un certain type (coercition de type ou downcast), ce qui revient à un test de sous-typage.

Avantages de la compilation globale

La connaissance de la totalité du code d’un programme et de son point d’entrée rend possible des analyses fines sur la façon dont chaque unité du programme est utilisée par les autres, ce qui permet de la compiler plus efficacement. Les améliorations attendues concernent la réduction de la taille du programme, du polymorphisme des envois de message et du coût des trois mécanismes propres aux langages à objets. Le surcoût de l’héritage multiple peut aussi être complètement éliminé.

Analyse de types

Le mécanisme d’envoi de messages est considéré comme le goulot d’étranglement des programmes à objets. Les statistiques montrent que la plupart des envois de messages sont en réalité des appels monomorphes : une analyse globale, souvent simple, permettrait de déterminer statiquement la méthode à appeler. Les langages proposent fréquemment des dispositifs permettant de déclarer qu’une méthode n’est pas soumise à la liaison tardive ( static en JAVA, absence de virtual en C++) mais un compilateur optimisé devrait permettre de s’en passer.
L’analyse de types, dont un grand nombre de techniques est décrit dans [GRO 01] et qu’il ne faut pas confondre avec l’inférence de types à la ML, permet de détecter les appels monomorphes et de réduire le polymorphisme des autres appels. Elle consiste à approximer trois groupes d’ensembles : l’ensemble des classes effectivement instanciées, celui des types dynamiques que pourra prendre chaque expression dans toutes les exécutions possibles (on l’appelle son type concret) et d’autre part l’ensemble des procédures potentiellement appelées pour chaque site d’envoi de messages. Ces trois groupes d’ensembles sont en dépendance circulaire, puisque les méthodes qui peuvent être appelées dépendent des types dynamiques du receveur, lesquels dépendent à leur tour des classes instanciées et ces dernières des méthodes effectivement appelées. Cette circularité explique la difficulté du problème [GIL 98] et la variété des solutions, toutes approximatives par excès. L’analyse de types permet donc de déterminer le code vivant — c’est-à-dire les classes instanciées ainsi que les méthodes appelées et les attributs utilisés, le reste constitue le code mort, qui n’a pas besoin d’être présent dans le programme final — tout en optimisant tout ce qui a trait au polymorphisme.

Implémentation des objets et de l’envoi de message par la coloration

La coloration s’inscrit dans le cadre des techniques d’implémentation avec tables de méthodes. L’implémentation des classes et des objets comporte deux parties : en mémoire dynamique, une zone pour chaque instance, contenant ses attributs et un pointeur vers sa classe ; en mémoire statique, une zone pour la classe, contenant les adresses des méthodes. Dans ce cadre, l’héritage multiple pose un problème, surtout en compilation séparée. C++ l’a résolu avec une implémentation par sous-objets, qui induit un surcoût important [LIP 96, DUC 02a]. Dans le pire des cas, le nombre de tables de méthodes est quadratique dans le nombre de classes (au lieu de linéaire) et la taille cubique (au lieu de quadratique). Dans l’implémentation des objets, les pointeurs sur ces tables peuvent être plus nombreux que les attributs de l’objet. Enfin, une référence à un objet dépend du type statique de la référence.
La coloration [DIX 89, PUG 90, COH 91, VIT 97, DUC 02b] permet de s’affranchir des surcoûts de l’héritage multiple en se ramenant à l’implémentation naturelle en héritage simple et typage statique. Elle s’applique aussi bien aux attributs et aux méthodes, qu’aux classes pour le test de sous-typage. La technique consiste à déterminer un identifiant par classe ainsi qu’une couleur par classe, méthode et attribut, de façon à garantir les invariants des implémentations de l’héritage simple en typage statique :
Invariant 1 Une référence à un objet ne dépend pas du type statique de la référence.
En corollaire, l’affectation ou le passage de paramètre polymorphe ne coûte rien.
Invariant 2 Un attribut (resp. une méthode) possède une couleur, sa position, invariante par spécialisation. Deux attributs (resp. méthodes) de même couleur n’appartiennent pas à la même classe. En corollaire, la position de la méthode ou de l’attribut ne dépend pas du type dynamique du receveur.
Invariant 3 Chaque classe possède un identifiant unique et une couleur. Deux classes de même couleur n’ont pas de sous-classe commune. La table de méthodes d’une classe contient, à la couleur de chaque super-classe, son identifiant. Vérifier que D est une sous-classe de C revient simplement à vérifier que tabD[kC] = idC, où tab est la table de méthodes, k la couleur et id l’identifiant.
La figure 1 schématise cette implémentation, en séparant la table des couleurs de classes de la table des méthodes, par clarté. Le respect de ces invariants est aisé, mais la minimisation de la taille des tables — c’est-à-dire du nombre d’entrées non occupées de ces tables, en grisé sur la figure — est un problème proche de la coloration de graphes et prouvé récemment NP-difficile [TAK 03]. Heureusement, les hiérarchies de classes constituent apparemment des instances faciles du problème et de nombreuses heuristiques ont été proposées, qui donnent des résultats satisfaisants, même sur de très grosses hiérarchies [PUG 90, DUC 01, DUC 03, TAK 03].

Limites de la compilation globale

La compilation globale n’est pas utilisée dans le milieu industriel (C, C++, ADA, etc.) pour des raisons qui tiennent autant de l’histoire que de contraintes imposées par le développement, l’administration ou l’exécution des programmes. De plus, la confidentialité du code source est difficile à préserver, alors que la compilation séparée permet de ne diffuser que les unités compilées.
Au cours du développement, le rôle d’un compilateur est double : vérifier la correction syntaxique et sémantique du programme et générer un exécutable pour le tester. Deux points sont donc à considérer : la qualité de cette vérification et le temps de génération. En compilation séparée, le compilateur remplit ces deux rôles de façon satisfaisante. En revanche, la compilation globale a le seul but de générer un exécutable : il n’y a pas de raison que le compilateur examine le code mort. Plus généralement, le code source peut être incorrect (d’après les spécifications du langage) mais celui d’une application correct, à cause de (ou grâce à) la spécialisation de code, qui consiste à traiter l’héritage ou la généricité par copie de code. Le code source d’une classe paramétrée ou d’une méthode « customisée » peut être incorrect dans la classe d’origine mais correct dans le contexte où ses spécialisations ont été insérées. Pour remédier à ce défaut, un compilateur global devrait donc être muni d’une fonctionnalité voisine d’un compilateur séparé, incluant au moins toutes les phases de la compilation qui peuvent générer des erreurs, jusqu’à la génération de code exclue.
En ce qui concerne le temps de compilation et de génération d’un exécutable, il est difficile de se prononcer sans un véritable banc d’essai mesurant la différence entre le temps passé aux optimisations et celui gagné en ne compilant pas le code mort ou comparant l’impact sur les compilations incrémentales liées aux cycles relativement courts d’édition, de modification et de test d’une unité de code.
Par ailleurs, la compilation globale semble difficilement compatible avec les bi-bliothèques dynamiques. En effet, celles-ci sont partagées au chargement ou à l’exécution afin de permettre une facilité d’administration et d’évolution des programmes.

Schéma de compilation séparée avec optimisations globales

Le schéma de compilation proposé dans cet article met en œuvre les deux phases habituelles de la compilation séparée. La première est ditelocale car son rôle est de compiler une unité de code indépendamment des programmes l’utilisant. La seconde phase est dite globale car elle assemble et adapte les unités compilées afin de construire un programme exécutable. Le code produit par la compilation séparée d’une unité contient dessymboles permettant de l’accrocher aux unités utilisées [LEV 99]. Lors de l’édition de liens, les codes des différentes unités sont concaténés et les sym-boles sont remplacés par les adresses numériques. Le schéma de compilation proposé ici diffère peu de ce schéma classique : la phase locale génère du code dans lequel les informations encore inconnues ne se réduisent pas à l’adresse de symboles, mais peuvent inclure des informations pour savoir s’il faut inclure une portion de code (code conditionnel) ou des symboles qui seront à remplacer par des valeurs (couleurs). Au total, il s’agit donc d’un code compilé normal, décoré de quelques balises.

Phase locale

Nous considérerons que la classe est l’unité de compilation. La phase locale prend en entrée le code source d’une classe et produit en sortie trois niveaux de code différents (figure 2). Le schéma externe de la classe décrit son interface et ses super-classes directes, sans le code. Le schéma interne est la représentation de la circulation des types dans les méthodes de la classe. Le code correspond à la sortie habituelle du compilateur, dans le langage cible de la compilation (généralement du code machine). Ces trois parties peuvent être incluses dans le même fichier ou dans des fichiers distincts mais le schéma externe doit pouvoir être disponible séparément. On n’oubliera pas les différents messages d’erreur et d’avertissement qui font le charme de la compilation.

Schémas externes des classes

La compilation d’une unité est indépendante des autres unités jusqu’à un certain point seulement car elle doit connaître l’interface des classes dont l’unité est sous-classe ou cliente. Cette interface peut être disponible, soit dans le schéma externe de la classe cliente parce qu’elle a déjà été compilée ou parce que ce schéma a été fourni séparément, soit dans le code source de la classe cliente. Dans ce dernier cas, une génération récursive du schéma externe sera nécessaire (figure 2).
Le schéma externe d’une classe peut être vu comme une instance du méta-modèle du langage. Son rôle est de fournir les briques élémentaires permettant à la phase glo-bale de construire le méta-modèle complet d’un programme. Il contient au moins le nom de la classe, ceux de ses super-classes directes, ainsi que ses propriétés, décrites au minimum par leur nom, leur signature et le nom symbolique désignant le code à exécuter. Le schéma externe ressemble donc à la notion d’interface, mais il ne se limite pas à la partie non privée. Dans un langage comme EIFFEL, le schéma externe contient aussi les assertions. Pour des raisons d’optimisations, il peut contenir des informations étendues à ses super-classes directes et indirectes. Ce genre d’optimisation est intéressant dans les langages où l’héritage est complexe (comme par exemple EIFFEL via les clauses de redéfinition), mais aussi pour la compilation de programmes utilisant des hiérarchies profondes. Ce dernier point peut s’illustrer en C++ par la technique de précompilation d’en-têtes qui peut diminuer, dans des cas réels, de plus de la moitié la durée de compilation d’un programme.