Translation and global optimization in class-based languages
Traduction et optimisation globale dans les langages de classes
Résumé
This work falls within the scope of research pertaining to the compilation of class-based languages --- especially Eiffel --- and more generally about the compilation of statically-typed object-oriented languages. In a nutshell, it can be said the aim of this thesis is to try to answer a fundamental question: how is it possible to better compile objet-oriented languages, that is, how is it possible to have faster and safer programs? This research work is mainly based on static analysis, with a two-pronged approach. The first axis consists in being able to do program validity and coherency checks, not only on finished programs but also from the beginning of the development, so as to be able to assist developers as much as possible during the design and implementation phase. The second axis --- the very core of this thesis --- considers the use of information coming from the system's static analysis to improve the generated code quality. Indeed, this kind of information offers important optimizations opportunities on the generated code, be it algorithm-based optimizations or data structures optimizations. We propose and experiment an approach based on code duplication and customization thanks to system-wide analysis, so as to efficiently implement the compiled program data structures and code, especially what pertains to late binding. We thus introduce a novel late binding method based on direct branching trees whose performance are greater than or equal to those of current classical systems relying on indirection tables. This approach is also extended to the generation by the compiler of a garbage collector which is automatically customized to the compiled application. We also carry some studies to evaluate the optimizations allowed by massive use of aliasing in a compiler written in a class-based language, as well as means to better handle this technique. This work is validated by, among other things, the development of an Eiffel compiler named SmallEiffel and its libraries, which, widely distributed and used, have become The GNU Eiffel Compiler.
Ce travail s'inscrit dans le cadre des recherches menées autour de la compilation des langages de classes, notamment Eiffel, et plus généralement des langages à objets à typage statique. Très brièvement, on peut dire que le but de cette thèse revient à tenter de répondre à une question fondamentale: comment mieux compiler les langages à objets, c'est à dire comment avoir des programmes plus rapides et plus sûrs ? Ce travail de recherche est basé en grande partie sur l'analyse statique, abordée via deux axes principaux. Le premier consiste à pouvoir effectuer des contrôles de validité et de cohérence du programme, et ce non seulement sur les programmes finis, mais bien dès le début du développement, de façon à pouvoir assister au maximum les développeurs durant la phase de conception et d'implantation. Le second axe, qui est la substance même de cette thèse, considère l'utilisation des informations apportées par l'analyse statique du système pour améliorer la qualité du code généré. En effet, ces informations offrent des possibilités importantes en terme d'optimisation du code généré, aussi bien par des optimisations liées aux algorithmes que par des optimisations sur les structures de données. Nous proposons et expérimentons une approche basée sur la duplication et la spécialisation du code par analyse globale du système, afin d'implanter de façon efficace les structures de données et le code du programme compilé, notamment en ce qui concerne la liaison dynamique. Nous introduisons ainsi une nouvelle méthode de liaison dynamique, basée sur des arbres de branchement directs, dont les performances sont supérieures ou égales à celles des systèmes actuels classiques à base de tables d'indirection. Cette approche est également étendue à la génération par le compilateur d'un ramasse-miettes automatiquement adapté à l'application compilée. Nous menons aussi certaines études pour évaluer les optimisations permises par l'utilisation massive de l'aliasing dans un compilateur écrit dans un langage de classes, ainsi que des moyens de mieux maîtriser cette technique. Ces travaux sont validés entre autres par le développement d'un compilateur Eiffel nommé SmallEiffel et de ses bibliothèques, qui, très largement diffusés et utilisés, sont devenus The GNU Eiffel Compiler.