Symbolic Range Analysis of Pointers

Abstract : Alias analysis is one of the most fundamental techniques that compilers use to optimize languages with pointers. However, in spite of all the attention that this topic has received, the current state-of-the-art approaches inside compilers still face challenges regarding precision and speed. In particular, pointer arithmetic, a key feature in C and C++, is yet to be handled satisfactorily. This paper presents a new alias analysis algorithm to solve this problem. The key insight of our approach is to combine alias analysis with symbolic range analysis. This combination lets us disambiguate fields within arrays and structs, effectively achieving more precision than traditional algorithms. To validate our technique, we have implemented it on top of the LLVM compiler. Tests on a vast suite of benchmarks show that we can disambiguate several kinds of C idioms that current state-of-the-art analyses cannot deal with. In particular, we can disambiguate 1.35x more queries than the alias analysis currently available in LLVM. Furthermore, our analysis is very fast: we can go over one million assembly instructions in 10 seconds.
Type de document :
Communication dans un congrès
International Symposium of Code Generation and Optmization, Mar 2016, Barcelona, Spain. Proceedings of CGO'16, pp.791-809, 2016, Code Generation and Optimization
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01228928
Contributeur : Laure Gonnord <>
Soumis le : vendredi 25 mars 2016 - 16:41:06
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : dimanche 26 juin 2016 - 15:21:42

Fichier

CGO16_RangeAlias_hal_authorver...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale 4.0 International License

Identifiants

  • HAL Id : hal-01228928, version 1

Collections

Citation

Vitor Paisante, Maroua Maalej, Leonardo Barbosa, Laure Gonnord, Fernando Magno Quintão Pereira. Symbolic Range Analysis of Pointers. International Symposium of Code Generation and Optmization, Mar 2016, Barcelona, Spain. Proceedings of CGO'16, pp.791-809, 2016, Code Generation and Optimization. 〈hal-01228928〉

Partager

Métriques

Consultations de la notice

448

Téléchargements de fichiers

209