Analyse de pointeurs pour l’optimisation de code dans LLVM

Sujet de projet recherche de master 2

Equipe : DART/Émeraude

Responsables HDR : Pierre Boulet (Lille) & Paul Feautrier (Lyon)

Encadrante/contact : Laure Gonnord. mail Laure.Gonnord at lifl.fr

Mots-clefs : Compilation efficace, analyse de programmes C, LLVM, pointeurs, modèle mémoire, interprétation abstraite.

Contexte :
Ce sujet se place à la frontière des thématiques de recherche Émeraude (Université Lille1 / Laboratoire d’Informatique Fondamentale de Lille) et Compsys (Inria / Éns Lyon).
L’avancée technologique des plateformes matérielles, avec des caractéristiques toujours plus complexes, rend nécessaire des analyses toujours plus fines du code source, que ce soit pour des buts d’optimisation à la compilation (optimisation de taille mémoire, de l’usage du cache. . .) ou d’optimisations lors de l’exécution.

L’équipe Compsys a une expérience dans la transformation de programme source à source, mais les programmes traités sont un noyau de C. L’équipe Émeraude a des expériences dans l’utilisation et l’optimisation des ressources à l’exécution, mais pour l’instant trop peu d’informations sur les programmes exécutés ne sont utilisées. L’implémentation d’une analyse de pointeurs est donc cruciale pour le passage à l’échelle de nos travaux (compilateurs, analyseurs, …) Ce stage se place dans le cadre d’une collaboration long terme entre les deux équipes.

Problématique :
L’analyse d’un programme utilisant des pointeurs est connu pour être un problème difficile, qui n’admet en général que des solutions approximatives et conservatives, lesquelles le plus souvent inhibent toute optimisation. Pour un panorama de la recherche sur le sujet, on consultera [1].
Or, on constate que très souvent, les pointeurs ne sont utilisés – en C – que de façon rudimentaire :
– transmission d’arguments par adresses
– allocation dynamique de tableaux
– descripteurs de tableaux
– pseudo-indices.
Le sujet du stage est la réalisation d’un outil de détection de ces usages simples. Le résultat de cette analyse préliminaire sont destinées aux phases suivantes d’un analyseur du genre de l’outil c2fsm [2] qui transforme le programme en un automate interprété. Pour éviter d’avoir à se plonger dans un logiciel complexe et peu documenté, on procédera de préférence en mode source-à-source, c’est-à-dire que l’on engendrera un nouveau programme C, débarrassé d’un maximum de pointeurs, et sémantiquement équivalent au programme original. Dans une étape ultérieure – qui ne fait pas partie du stage – on essaiera de générer directement un représentation intermédiaire (RI) conforme à celle de l’outil, et incluant les résultats de l’analyse.

Travail à réaliser : l’étudiant devra faire une étude bibliographique des analyses de pointeurs, choisir les plus simples algorithmiquement, et éventuellement en construire de nouvelles. Il validera ses travaux par un prototype basé sur le framework LLVM. Des idées directrices ont été rédigées dans la version longue de ce sujet.

Requis : Bonnes connaissances en C et en théorie de la compilation. Une familiarité avec LLVM et son langage d’implémentation (C++) serait appréciée.

Apport et suite : Les compétences acquises lors du stage pourront être valorisées dans l’industrie car LLVM est un framework de plus en plus utilisé. Le stagiaire pourra poursuivre ses travaux dans le cadre d’une thèse (sous réserve de financement).

Bibliographie :

  • [1] Michael Hind. Pointer analysis : Haven’t we solved this problem yet ? In PASTE’01, pages 54–61. ACM Press, 2001.
  • [2] Paul Feautrier and Laure Gonnord. Accelerated Invariant Generation for C Programs with Aspic and C2fsm. In Workshop on Tools for Automatic Program AnalysiS, TAPAS’10, Perpignan, France, September 2010.
  • [3] Björn Franke and Michael O’Boyle. Array recovery and high-level transformations for dsp applications. ACM Trans. Embed. Comput. Syst., 2(2) :132–162, May 2003.
Tweet about this on TwitterShare on LinkedInShare on Google+Share on FacebookEmail this to someone