Combining Range and Inequality Information for Pointer Disambiguation

Abstract : Pentagons is an abstract domain invented by Logozzo and Fähndrich to validate array accesses in low-level programming languages. This algebraic structure provides a cheap “less-than check”, which builds a partial order between the integer variables used in a program. In this paper, we show how we have used the ideas available in Pentagons to design and implement a novel alias analysis. This new algorithm lets us disambiguate pointers with offsets, so common in C-style pointer arithmetics, in a precise and efficient way. Together with this new abstract domain we describe several implementation decisions that lets us produce a practical pointer disambiguation algorithm on top of the LLVM compiler. Our alias analysis is able to handle programs as large as SPEC’s gcc in a few minutes. Furthermore, we have been able to improve the percentage of pairs of pointers disambiguated, when compared to LLVM’s built-in analyses, by a four-fold factor in some benchmarks.
Document type :
Reports
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/hal-01429777
Contributor : Maroua Maalej <>
Submitted on : Sunday, June 11, 2017 - 12:56:02 PM
Last modification on : Thursday, November 21, 2019 - 2:26:59 AM
Long-term archiving on : Wednesday, December 13, 2017 - 6:45:54 AM

File

RR-9076.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01429777, version 2

Collections

Citation

Maroua Maalej, Vitor Paisante, Fernando Magno Quintão Pereira, Laure Gonnord. Combining Range and Inequality Information for Pointer Disambiguation. [Research Report] RR-9076, ENS Lyon; CNRS; INRIA. 2016. ⟨hal-01429777v2⟩

Share

Metrics

Record views

169

Files downloads

496