![[English]](america.gif)
![[Index]](flech_g.gif)
Les langages de programmation récents comme ML ou Java offrent souvent un mécanisme de récupération automatique de la mémoire allouée en tas, le garbage collector ou glaneur de cellules. Cependant, le mécanisme de garbage collection (GC) prend du temps à l'exécution. Mon stage de DEA et ma thèse ont eu pour but d'étudier l'analyse d'échappement, technique fondée sur l'interprétation abstraite, qui permet d'allouer les données en pile plutôt que dans le tas, soulageant ainsi la charge du GC.
Mon stage de DEA a eu lieu d'avril à septembre 1996 à l'INRIA Rocquencourt, sous la direction d'Alain Deutsch. J'ai ensuite continué ce travail pendant ma thèse toujours avec Alain Deutsch à l'INRIA Rocquencourt, sous la direction de Patrick Cousot. Je l'ai soutenue le 7 décembre 2000, à l'Ecole Polytechnique. Voici son résumé.
L'analyse d'échappement est une analyse statique visant à déterminer si la durée de vie des données dépasse leur portée statique. Si elle ne la dépasse pas, les données peuvent être allouées en pile. Cette thèse étend les travaux précédents sur l'analyse d'échappement en traitant pour la première fois complètement deux langages réalistes : Objective Caml et Java. Nos contributions sont à la fois théoriques et pratiques.
Le principal apport théorique est la preuve de correction des analyses à partir d'une sémantique du langage analysé, en utilisant les techniques de l'interprétation abstraite. Pour ML, les opérations impératives (affectations), le polymorphisme, les fonctions d'ordre supérieur, les types récursifs sont traités. Deux représentations des valeurs abstraites d'échappement sont proposées : l'une, très efficace, utilise des entiers et l'autre, plus précise mais plus coûteuse, des types annotés. La comparaison entre ces deux représentations permet de trouver laquelle offre le meilleur compromis. Pour Java, nous proposons une nouvelle technique permettant de prendre en compte les affectations de façon plus précise que pour ML, tout en conservant une analyse rapide.
Une implantation complète dans des compilateurs a été effectuée, afin d'étudier deux applications de l'analyse d'échappement : l'allocation en pile et l'élimination des synchronisations (cette dernière application ne concerne pas ML). Les effets de ces optimisations font l'objet d'une étude expérimentale détaillée sur de gros programmes. Cette étude a montré que l'allocation en pile améliore la localité des données, diminue la charge du GC (glaneur de cellules) et le temps d'allocation, et que ses effets dépendent considérablement du type de GC et de cache utilisé. Les algorithmes utilisés ont été choisis de façon à fournir des analyses particulièrement efficaces. L'expérience a montré que la représentation utilisant des entiers est celle qui donne le meilleur rapport coût/précision.