Soutenance mémoire
De très nombreux travaux de recherche ont déjà été consacrés à l’analyse statique des pointeurs utilisés dans le langage C, et ce depuis plus d’une vingtaine d’années. Ce sujet est réputé difficile à cause de sa complexité en temps et en espace et à cause de la sémantique du langage C. De nombreuses analyses publiées ont de surcroît la réputation de contenir des erreurs, et seules les analyses les plus simples sont actuellement intégrées dans des compilateurs de production.
Nos motivations pour aborder à nouveau le sujet sont essentiellement constituées de besoins industriels actuels dans le domaine du traitement du signal. Ce dernier comporte de nombreuses applications écrites en langage C où des descripteurs de tableaux sont codés sous la forme d’un champ de structure de données contenant des pointeurs rendant les tâches d’optimisation de code et de parallélisation impossibles aux compilateurs. Les tableaux de structures de données sont aussi fréquemment utilisés dans les codes scientifiques, entre autres pour représenter les nombres complexes. La parallélisation de tels codes nécessite donc que l’analyse prenne en compte les champs de structures. Par ailleurs, certains codes scientifiques sont écrits de manière à pouvoir se passer d’un optimiseur dans le compilateur. Ils s’appuient uniquement sur des pointeurs pour représenter les tableaux et sur l’arithmétique des pointeurs pour les parcourir. L’analyse des opérations sur pointeurs est donc nécessaire pour leur parallélisation ou optimisation. Malheureusement, les travaux de recherche déjà effectués manquent parfois d’explications et de résultats concrets, ce qui ne permet pas de les reprendre, de les étendre et de les intégrer aux compilateurs et outils actuels. Enfin, une difficulté supplémentaire est que nous souhaitons effectuer l’analyse au niveau du code source tel qu’il a été écrit par le programmeur plutôt que sur une représentation trois adresses afin de permettre un retour simple vers le programmeur et une intégration dans un outil source-à-source.
L’importance du langage C
Le langage C a l’avantage d’être un langage de bas niveau, dont la syntaxe contient de nombreuses constructions avancées, et qui bénéficie aussi des avantages d’un langage de bas niveau, proche du matériel. De plus, le langage C est très portable : presque toutes les plateformes ont un compilateur C. Il permet la manipulation de la mémoire, de périphériques comme les disques durs ainsi que la communication avec les contrôleurs ou les processeurs. Durant ces dernières années il s’est imposé comme le langage de référence pour l’écriture d’applications scientifiques et il a été classé premier au classement 2012 des langages de programmation ,dans des domaines comme la mécanique de fluides, l’algorithmique géométrique, la biologie algorithmique, le traitement d’images, les mathématiques appliquées ou encore le traitement du signal [gnu91] [gnu96] [mat88] [mat70].
Les pointeurs en C
Une des particularités du langage C est la présence des pointeurs, qui sont des valeurs contenant l’adresse ou l’emplacement d’un objet ou d’une fonction dans la mémoire. C’est en «déréférençant» ces pointeurs que nous pouvons écrire ou lire les variables dites pointées. L’utilisation des pointeurs est fréquente en C notamment pour manipuler des chaînes de caractères, des tableaux dynamiques, des structures de données récursives dont les graphes et les arbres pour lesquels les nœuds sont créés dynamiquement, mais aussi pour parcourir efficacement les tableaux statiques. Le langage offre la possibilité de manipuler la mémoire en allouant et libérant des zones mémoire via des routines comme malloc ou free, mais cette liberté n’est pas sans danger. En effet, la manipulation des pointeurs est une opération délicate qui requiert expertise et attention de la part des développeurs. Beaucoup d’erreurs résultant d’une mauvaise gestion des pointeurs ne sont pas détectables à la compilation et aboutissent à l’interruption de l’exécution. Parmi ces erreurs figurent les pointeurs non initialisés (appelés « wild pointer »), les pointeurs libérés puis réutilisés (appelés « dangling pointer »), les zones mémoire dont les références sont perdues avant qu’elles ne soient libérées (appelées fuites mémoire), ainsi que les pointeurs vers des variables de la pile disparues après une sortie de bloc ou de fonction. Un autre avantage et en même temps une difficulté de l’utilisation des pointeurs est l’usage de la notation tableau pour accéder au contenu d’un pointeur et vice-versa .
int main(){
int i = 1, *X = &i, Y[10] ;
X[i] = 2;
Y[i] = 1;
return 0;
}
Motivations
Importance de l’optimisation des programmes
Malgré l’évolution des architectures parallèles, illustrées par le circuit CELL [PBD], BlueGene/L [TDD+02] ou CRAY [JVIW05]), et des langages parallèles, comme par exemple OpenMP [DM98], MPI [SOHL+98] ou CUDA [NBGS08], de nombreux programmeurs continuent à réfléchir et concevoir leurs applications de manière séquentielle. En effet la parallélisation et l’optimisation requièrent des connaissances sur les dépendances entre données et instructions, la synchronisation ainsi que la gestion des communications inutiles en général pour le développeur et créent des problèmes supplémentaires de mise au point. À cela s’ajoute aussi le nombre important d’applications scientifiques existantes et qui sont candidates aux optimisations. Pour ces raisons, les développeurs préfèrent laisser le soin de la parallélisation et de l’optimisation aux compilateurs actuels qui sont maintenant munis d’options permettant d’effectuer ces tâches comme par exemple pour le compilateur gcc. L’utilisation de l’option « gcc icc xlc + OpenMP ou MPI » permet de gérer dans le code les paradigmes de parallélisation OpenMP ou MPI.
D’autres outils de recherche permettant la parallélisation et l’optimisation automatiques existent. PSarmi eux nous citons PIPS [AAC+] [ACSGK11], PLUTO [BHR08], Polaris [BEF+94], Omni OpenMP [KSS00] et SUIF [AALwT93]. Ces outils agissent soit au moment de la compilation pour réaliser des analyses statiques, soit au moment de l’exécution pour réaliser des analyses dynamiques. Elles détectent les portions de code qui peuvent être optimisées ou parallélisées comme par exemples les nids de boucles. Les outils d’optimisation sont utilisés essentiellement pour améliorer les performances des application de traitement de signal. Le traitement du signal est la discipline qui développe et étudie les techniques de traitement (filtrage, détection…), d’analyse et d’interprétation des signaux. D’autres applications sont des candidates aux optimisations comme par exemple le traitement d’images, qui désigne une discipline des mathématiques appliquées qui étudie les images numériques et leurs transformations, dans le but d’améliorer leur qualité ou d’en extraire de l’information. L’amélioration ou l’extraction de l’information à partir des images se fait par l’application de filtres, qui sont des convolutions appliquées à l’image représentée sous la forme d’un tableau multidimensionnel. Donc ces applications contiennent beaucoup de calcul sur des éléments de tableaux, ce qui fait d’elles les candidates idéales pour la parallélisation des nids de boucles. La phase de parallélisation nécessite de vérifier que les instructions ou occurrences d’instructions sont indépendantes les unes par rapport aux autres. Ceci concerne en particulier les itérations de boucles. C’est ce qu’on appelle l’analyse de dépendances. D’autres optimisations ont besoin d’une information précise sur les pointeurs ; parmi elles nous citons la suppression du code inutile, la propagation de constantes ou encore la suppression de sous-expressions communes .
La mémoire d’un programme
Avant de préciser les optimisations faites sur les codes, précisons que, lors de l’exécution d’un programme, une plage mémoire lui est allouée. Elle est généralement divisée en cinq segments, chacun ayant une fonctionnalité bien précise :
1. « text » : appelé aussi segment code. Il sert à stocker les instructions machine du programme ;
2. « data » : il contient les variables globales initialisées au lancement du programme, les chaînes de caractères et les constantes globales ;
3. « bss » : contient le reste des variables globales et statiques (non-initialisées) ;
4. « heap » : appelé aussi tas, c’est une zone mémoire utilisée pour l’allocation dynamique. Cette zone permet au programmeur, à des moments arbitraires de l’exécution, de demander au système l’allocation de nouvelles zones de mémoire, et de restituer au système ces zones (libérer la mémoire) ; la manipulation de la mémoire est possible via les routines de la bibliothèque standard de C.
5. « stack » : appelé pile, il a pour objectif le stockage des variables locales des fonctions ainsi que le contexte de ces dernières.
Optimisation des programmes en présence de pointeurs
La présence des pointeurs dans un programme créé une réelle incertitude sur les données accédées par les instructions. Les variables sont modifiées via le déréférencement de pointeurs. En l’absence d’information sur l’emplacement mémoire vers lequel le pointeur pointe, il est nécessaire d’analyser le programme sous l’hypothèse que toutes les variables du programme peuvent être lues ou écrites par chaque déréférencement. Deux pointeurs peuvent pointer vers le même emplacement ; par exemple pour le programme 1.2, chaque déréférencement du pointeur p ou q pourrait être considéré comme une lecture (ou écriture) des variables i ou j.
int main()
{
int i = 1, j=0, *p, *q;
p = &i; // S1
q = p; // S2
*q = 2; // S3
j = *p; // S4
return 0;
}
Prog 1.2 – p et q pointent vers la même zone mémoire après S2 .
|
Table des matières
1 Introduction
1.1 Contexte
1.1.1 L’importance du langage C
1.1.2 Les pointeurs en C
1.2 Motivations
1.2.1 Importance de l’optimisation des programmes
1.2.2 La mémoire d’un programme
1.2.3 Optimisation des programmes en présence de pointeurs
1.3 Problématiques
1.3.1 Détermination des cibles de pointeurs
1.3.2 Analyse de pointeurs ou d’alias ?
1.3.3 Analyser les structures de données récursives
1.3.4 Abstraction de la mémoire
1.4 Contributions
1.4.1 Traiter toutes les instructions du langage C ?
1.4.2 Concevoir une analyse intraprocédurale précise
1.4.3 Concevoir une analyse interprocédurale modulaire
1.4.4 Répondre aux besoins des applications scientifiques
1.4.5 Modéliser l’allocation dynamique au niveau du tas
1.5 Structure de la thèse
2 Les analyses clientes et les objectifs pour le compilateur
2.1 La représentation des arcs points-to
2.1.1 Structure de données
2.1.2 Affichage de la relation points-to
2.1.3 Conclusion
2.2 Les effets mémoire et l’analyse des pointeurs
2.2.1 Définitions
2.2.2 Les effets en présence de pointeurs
2.3 Les chaînes « use-def » et la suppression du code inutile
2.3.1 Les chaînes « use-def »
2.3.2 Suppression de code inutile
2.3.3 Les chaînes use-def et la suppression de code inutile sans information points-to
2.3.4 Chaînes use-def et suppression de code inutile avec l’information points-to
2.3.5 Conclusion
2.4 L’analyse des dépendances et la parallélisation
2.4.1 L’analyse des dépendances et la parallélisation sans information points-to
2.4.2 L’analyse des dépendances et la parallélisation avec l’information points-to
2.4.3 Conclusion
2.5 La suppression de sous-expressions communes
2.5.1 La suppression de sous-expressions communes sans information sur les pointeurs
2.5.2 La suppression de sous-expressions communes avec l’information sur les pointeurs
2.5.3 Conclusion
2.6 Le renommage des scalaires
2.6.1 Le renommage des scalaires sans information points-to
2.6.2 Le renommage des scalaires avec l’information points-to
2.7 Conclusion
3 État de l’art : Les analyses de pointeurs
3.1 Les analyses insensibles au flot et au contexte
3.1.1 L’analyse d’Andersen
3.1.2 L’analyse de Steensgaard
3.1.3 Conclusion
3.2 Les analyses sensibles au contexte et au flot de contrôle
3.2.1 L’analyse de Wilson
3.2.2 L’analyse d’Emami
3.2.3 Comparaison des analyses insensibles au flot et au contexte
3.2.4 Comparaison des analyses sensibles au flot et au contexte
3.3 Autres travaux
3.3.1 L’analyse « pointer values »
3.3.2 L’allocation dynamique
3.3.3 L’union, l’arithmétique sur pointeurs et le cast
3.4 Conclusion
4 L’analyse intraprocédurale simplifiée
4.1 Définition de la syntaxe abstraite utilisée pour C
4.2 Définition du langage L0
4.2.1 Définition des domaines
4.2.2 Syntaxe du langage L0
4.2.3 Typage des expressions
4.3 Le schéma général de l’analyse points-to
4.3.1 Graphe des appels de l’analyseur et résultat de l’analyse
4.3.2 Étapes de l’analyse points-to
4.3.3 Traduction des expressions d’adresses en chemins d’accès mémoire constants (CP)
4.4 Définition de l’analyse points-to pour le langage L0
4.4.1 L’opérateur d’assignation d’un opérateur
4.4.2 Exemples
4.5 Définition du langage L1
4.5.1 Langage L1 et notations
4.5.2 Les points de séquence
4.5.3 Rupture de contrôle : exit()
4.5.4 Rupture de contrôle : return
4.6 Les expressions en langage L1
4.6.1 Définition de l’analyse points-to pour le langage L1
4.6.2 Cas des branchements conditionnels «if then…else »
4.7 Conclusion
5 L’analyse intraprocédurale étendue
5.1 Cas particuliers d’emplacements mémoire abstraits
5.1.1 Modélisation de NULL
5.1.2 Modélisation des pointeurs non initialisés
5.1.3 Modélisation des tableaux de pointeurs
5.1.4 Modélisation des constantes entières
5.1.5 Conclusion
5.2 Modélisation de l’allocation dynamique
5.2.1 Modélisation du tas
5.2.2 Modélisation d’un appel à « malloc »
5.2.3 Modélisation d’un appel à free
5.2.4 Détection des erreurs liées à l’allocation mémoire
5.2.5 Conclusion
5.3 Abstraction de l’ensemble des adresses sous forme de treillis
5.3.1 Opérateurs et structure du treillis des chemins constants CP
5.3.2 Le sous-treillis Module
5.3.3 Le sous-treillis des noms de variables N ame
5.3.4 Le treillis T ype
5.3.5 Le treillis des indices V ref
5.3.6 Le prédicat d’atomicité sur le treillis CP
5.3.7 Conclusion
5.4 Les choix de conception
5.4.1 L’initialisation des paramètres formels à NULL
5.4.2 Impact de l’initialisation à NULL sur l’interprétation des conditions
5.4.3 L’utilisation des alias
5.4.4 Conclusion
5.5 Treillis des relations points-to PT
5.5.1 Abstraction de la valeur d’un pointeur avec une relation points-to
5.5.2 Domaine des relations points-to
5.5.3 Typage d’un arc points-to
5.5.4 Ordre sur les relations points-to
5.5.5 Finitude des relations
5.5.6 Typage des arcs points-to
5.6 Utilisation des treillis CP et PT
5.6.1 Calcul des ensembles Kill et Gen : affectation d’un pointeur
5.6.2 Cas des boucles
5.6.3 Cas de la boucle « while »
5.6.4 Cas de la boucle for
5.6.5 La boucle do…while
5.6.6 L’algorithme général any_loop_to_points_to()
5.6.7 Conclusion sur les boucles
5.6.8 Cas des graphes de flot de contrôle, « unstructured »
5.7 Finitude de la représentation/abstraction de la relation points-to
5.7.1 Nombre de déréférencements
5.7.2 Longueur des chemins dans le graphe
5.7.3 Nombre de nœuds du graphe points-to
5.7.4 Nombre d’arcs points-to sortants d’un nœud
5.7.5 Conclusion
5.8 Conclusion
6 Conclusion
