Runtime pointer disambiguation

Abstract : In order to optimize code effectively, compilers must deal with memory dependences. However, the state-of-the-art heuristics available in the literature to track memory dependencies are inherently imprecise and computationally expensive. Consequently, the most advanced code transformations that compilers have today are ineffective when applied on real-world programs. The goal of this paper is to solve this conundrum through the hybrid disambiguation of pointers. We provide a static analysis that generates dynamic tests to determine when two memory locations can overlap. We then produce two versions of a loop: one that is aliasing-free - hence, easy to optimize - and another that is not. Our checks lets us safely branch to the optimizable region. We have applied these ideas on polly-llvm, a loop optimizer built on top of the llvm compilation infrastructure. Our experiments indicate that our method is precise, effective and useful: we can disambiguate every pair of pointer in the loop intensive polybench benchmark suite. The result of this precision is code quality: the binaries that we generate are 10% faster than those that polly-llvm produces without our optimization, at the -O3 optimization level of llvm. Given the current technology to statically solve alias analysis, we believe that our ideas are a necessary step to make modern compiler optimizations useful in practice.
Complete list of metadatas
Contributor : Fabrice Rastello <>
Submitted on : Thursday, November 26, 2015 - 11:10:03 AM
Last modification on : Wednesday, April 17, 2019 - 7:22:02 PM


  • HAL Id : hal-01234086, version 1


Péricles Alves, Fabian Gruber, Johannes Doerfert, Alexandros Lambrineas, Tobias Grosser, et al.. Runtime pointer disambiguation. Proceedings of the 2015 International Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2015, Oct 2015, Pittsburgh, United States. pp.18. ⟨hal-01234086⟩



Record views