Symbolic range analysis of pointers
Symbolic range analysis of pointers
复制标题
指针的符号范围分析
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Fernando Magno Quintão Pereira
中科院分区：
文献类型：
--
作者：
Vitor Paisante;Maroua Maalej;Leonardo B. Oliveira;L. Gonnord;Fernando Magno Quintão Pereira
指针分析是编译器用来优化具有指针的语言的最基本的技术之一。然而，尽管这个主题受到了广泛的关注，但编译器内部目前最先进的方法仍然面临着精度和速度方面的挑战。特别是，C和C++中的一个关键特性指针算法还没有得到令人满意的处理。本文提出了一种新的别名分析算法来解决这个问题。我们的方法的关键见解是结合联合收割机别名分析与符号范围分析。这种组合使我们能够消除数组和结构中字段的歧义，有效地实现比传统算法更高的精确度。为了验证我们的技术，我们在LLVM编译器上实现了它。对大量基准测试的测试表明，我们可以消除当前最先进的分析无法处理的几种C习惯用法的歧义。特别是，我们可以消除比LLVM中当前可用的别名分析多1.35倍的查询。此外，我们的分析速度非常快：我们可以在10秒内处理超过100万条汇编指令。
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.