Points to analysis for the C language

Les analyses statiques ont pour but de déterminer les propriétés des programmes au moment de la compilation. Contrairement aux analyses dynamiques, le comportement exact du programme ne peut être connu. Par conséquent, on a recours à des approximations pour remédier à ce manque d'information. Malgré ces approximations, les analyses statiques permettent des optimisations et des transformations efficaces pour améliorer les performances des programmes. Parmi les premières analyses du processus d'optimisation figure l'analyse des pointeurs. Son but est d'analyser statiquement un programme en entrée et de fournir en résultat une approximation des emplacements mémoire vers lesquels pointent ses variables pointeurs. Cette analyse est considérée comme l'une des analyses de programmes les plus délicates et l'information qu'elle apporte est très précieuse pour un grand nombre d'autres analyses clientes. En effet, son résultat est nécessaire à d'autres optimisations, comme la propagation de constante, l'élimination du code inutile, le renommage des scalaires ainsi que la parallélisation automatique des programmes. L'analyse des pointeurs est très nécessaire pour l'exploitation du parallélisme présent dans les applications scientifiques écrites en C. Ceci est dû au fait que les tableaux, très présents dans ce type d'applications, sont accédés via les pointeurs. Il devient nécessaire d'analyser les dépendances entre les éléments de tableau dans le but de paralléliser les boucles. Le langage C présente beaucoup de difficultés lors de son analyse par la liberté qu'il offre aux utilisateurs pour gérer et manipuler la mémoire par le biais des pointeurs. Ces difficultés apparaissent par exemple lors de l'accès aux tableaux par pointeurs, l'allocation dynamique (via «malloc») ainsi que les structures de données récursives. L'un des objectifs principaux de cette thèse est de déterminer les emplacements mémoire vers lesquels les pointeurs pointent. Ceci se fait en assurant plusieurs dimensions comme : - la sensibilité au flot de contrôle, c'est-à-dire la mise à jour des informations d'un point programme à un autre ; - la non-sensibilité au contexte, c'est-à-dire l'utilisation de résumés au lieu de l'analyse du corps de la fonction à chaque appel ; - la modélisation des champs pointeurs des structures de données agrégées, dans laquelle chaque champ représente un emplacement mémoire distinct. D'autres aspects sont pris en compte lors de l'analyse des programmes écrits en C comme la précision des emplacements mémoire alloués au niveau du tas, l'arithmétique sur pointeurs ou encore les pointeurs vers tableaux. Notre travail permet l'amélioration des résultats des analyses clientes et en particulier il permet la parallélisation des boucles lorsqu'on accède aux éléments de tableaux via les pointeurs, la détection de code inutile ou le calcul du graphe de dépendances. Il est implémenté dans le compilateur parallélliseur PIPS (Parallélisation Interprocédurale de Programmes Scientifiques) et permet d'analyser, en particulier, les applications scientifiques de traitement du signal tout en assurant une analyse intraprocédurale précise et une analyse interprocédurale efficace via les résumés.Static analysis algorithms strive to extract the information necessary for the understanding and optimization of programs at compile time. The potential values of the variables of type pointer are the most difficult information to determine. This information is often used to assess if two pointers are potential aliases, i.e. if they can point to the same memory area. An analysis of pointers, also called points-to analysis, may provide more precision to other analyses such as constant propagation, analysis of dependencies or analysis of live variables. The analysis of pointers is very important for the exploitation of parallelism in scientific C programs since the most important structures they manipulate are arrays, which are typically accessed by pointers. It is necessary to analyse the dependencies between arrays in order to exploit the parallelism between loops. C language is very hard to analyse since it allows to users to manipulate the memory through pointers. These difficulties arise for example when accessing arrays by pointers, dynamic allocation (via "malloc") and recursive data structures. Points-to analysis may also attempt to handle recursive data structures and other structures that are accessed by pointers. This work provides a points-to analysis which is : - flow-sensitive, by taking into account the order of execution of instructions ; - field-sensitive, since structure fields are treated as individual locations ; - context-insensitive, because functions summaries are computed to avoid re-analyzing functions bodies. Other issues such as heap modeling, pointer arithmetics and pointers to arrays are also taken into account while analyzing C programs. Our intraprocedural analysis provides precise results to client analyses, in particular it allows parallelization when accessing the array elements loops via pointers, detecting useless code or computing the dependency graph. while our interprocedural one allows to propagate them efficiently. Our work is implemented within the PIPS (Parallélisation Interprocédurale de Programmes Scientifiques) parallelizer, a framework designed to analyze, optimize and parallelize scientific and signal processing applications. Keywords : static analysis, points-to analysis, flow-sensitive, context-insensitive, field-sensitive