Low-cost memory analyses for efficient compilers - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Thèse Année : 2017

Low-cost memory analyses for efficient compilers

Analyses de mémoire à bas coût pour des compilateurs efficaces

Résumé

This thesis was motivated by the emergence of massively parallel processing and supercomputing that tend to make computer programming extremely performing. Speedup, the power consump- tion, and the efficiency of both software and hardware are nowadays the main concerns of the information systems community. Handling memory in a correct and efficient way is a step toward less complex and more performing programs and architectures. This thesis falls into this context and contributes to memory analysis and compilation fields in both theoretical and experimental aspects. Besides the deep study of the current state-of-the-art of memory analyses and their limitations, our theoretical results stand in designing new algorithms to recover part of the imprecision that published techniques still show. Among the present limitations, we focus our research on the pointer arithmetic to disambiguate pointers within the same data structure. We develop our analyses in the abstract interpretation framework. The key idea behind this choice is correctness, and scalability: two requisite criteria for analyses to be embedded to the compiler construction. The first alias analysis we design is based on the range lattice of integer variables. Given a pair of pointers defined from a common base pointer, they are disjoint if their offsets cannot have values that intersect at runtime. The second pointer analysis we develop is inspired from the Pentagon abstract domain. We conclude that two pointers do not alias whenever we are able to build a strict relation between them, valid at program points where the two variables are simultaneously alive. In a third algorithm we design, we combine both the first and second analysis, and enhance them with a coarse grained but efficient analysis to deal with non related pointers. We implement these analyses on top of the LLVM compiler. We experiment and evaluate their performance based on two metrics: the number of disambiguated pairs of pointers compared to common analyses of the compiler, and the optimizations further enabled thanks to the extra precision they introduce.
La rapidité, la consommation énergétique et l’efficacité des systèmes logiciels et matériels sont devenues les préoccupations majeures de la communauté informatique de nos jours. Gérer de manière correcte et efficace les problématiques mémoire est essentiel pour le développement des programmes de grande tailles sur des architectures de plus en plus complexes. Dans ce contexte, cette thèse contribue aux domaines de l’analyse mémoire et de la compilation tant sur les aspects théoriques que sur les aspects pratiques et expérimentaux. Outre l’étude approfondie de l’état de l’art des analyses mémoire et des différentes limitations qu’elles montrent, notre contribution réside dans la conception et l’évaluation de nouvelles analyses qui remédient au manque de précision des techniques publiées et implémentées. Nous nous sommes principalement attachés à améliorer l’analyse de pointeurs appartenant à une même structure de données, afin de lever une des limitations majeures des compilateurs actuels. Nous développons nos analyses dans le cadre général de l’interprétation abstraite « non dense ». Ce choix est motivé par les aspects de correction et d’efficacité : deux critères requis pour une intégration facile dans un compilateur. La première analyse que nous concevons est basée sur l’analyse d’intervalles des variables entières ; elle utilise le fait que deux pointeurs définis à l’aided’un même pointeur de base n’aliasent pas si les valeurs possibles des décalages sont disjointes. La seconde analyse que nous développons est inspirée du domaine abstrait des Pentagones ; elle génère des relations d’ordre strict entre des paires de pointeurs comparables. Enfin, nous combinons et enrichissons les deux analyses précédentes dans un cadre plus général. Ces analyses ont été implémentées dans le compilateur LLVM. Nous expérimentons et évaluons leurs performances, et les comparons aux implémentations disponibles selon deux métriques : le nombre de paires de pointeurs pour lesquelles nous inférons le non-aliasing et les optimisations rendues possibles par nos analyses.
Fichier principal
Vignette du fichier
PhD.pdf (3.04 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

tel-01626398 , version 1 (30-10-2017)
tel-01626398 , version 2 (11-12-2017)

Identifiants

  • HAL Id : tel-01626398 , version 1

Citer

Maroua Maalej. Low-cost memory analyses for efficient compilers. Computer Science [cs]. UNIVERSITÉ DE LYON, 2017. English. ⟨NNT : ⟩. ⟨tel-01626398v1⟩
590 Consultations
755 Téléchargements

Partager

Gmail Facebook X LinkedIn More