Pointer disambiguation via strict inequalities
Pointer disambiguation via strict inequalities
复制标题
通过严格的不等式消除指针歧义
DOI：
10.1109/cgo.2017.7863735
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Fernando Magno Quintão Pereira
中科院分区：
文献类型：
--
作者：
Maroua Maalej;Vitor Paisante;P. Ramos;L. Gonnord;Fernando Magno Quintão Pereira
自编译器建设初期以来，静态分析的设计和实施一直是研究的重点。在这种情况下出现的挑战之一是对支持指针算术的语言分析，例如C，C ++和汇编方言。本文有助于解决这一挑战。我们从一个明显但没有探索的观察开始：如果指针严格少于另一个指针，它们就不能别名。在这一说法的激励下，我们使用抽象的解释来建立指示之间严格的关系。我们构建一个程序表示，将静态单个信息（SSI）属性授予我们的数据流分析。 SSI给了我们稀疏的算法，其正确性很容易确保。我们已经在LLVM中实施了静态分析。它在程序变量的数量上是线性运行的，并且根据基准测试，它的精确度是该编译器中已经采用的指针歧义技术的精确六倍。
The design and implementation of static analyses that disambiguate pointers has been a focus of research since the early days of compiler construction. One of the challenges that arise in this context is the analysis of languages that support pointer arithmetics, such as C, C++ and assembly dialects. This paper contributes to solve this challenge. We start from an obvious, yet unexplored, observation: if a pointer is strictly less than another, they cannot alias. Motivated by this remark, we use abstract interpretation to build strict less-than relations between pointers. We construct a program representation that bestows the Static Single Information (SSI) property onto our dataflow analysis. SSI gives us a sparse algorithm, whose correctness is easy to ensure. We have implemented our static analysis in LLVM. It runs in time linear on the number of program variables, and, depending on the benchmark, it can be as much as six times more precise than the pointer disambiguation techniques already in place in that compiler.