Analyse des pointeurs pour le langage C

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.

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 .

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  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. Chaque fois qu’une fonction est activée, une zone Pour un programme écrit en langage C, la manipulation de la mémoire se fait souvent via des pointeurs et l’allocation dynamique. Analyser l’état de la mémoire d’un programme est une tâche difficile à réaliser mais permet d’optimiser le coût des accès mémoire qui se font par le déréférencement de pointeurs, d’où la nécessité d’avoir une analyse de pointeurs ou d’alias  afin de de déterminer les cibles des pointeurs au niveau de la pile ou encore les cibles des pointeurs sur fonctions.

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.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

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 Conclusion

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.