激进域敏感基于合并的指针分析

An Aggressively Field-Sensitive Unification-Based Pointer Analysis

指针分析是静态程序分析的基础,指针分析的精度直接影响后续的程序分析和优化.域敏感性用来描述指针分析是否需要区分结构体对象的不同域成员.文中提出一种激进的基于合并的域敏感指针分析方法,利用目标机器模型中的数据布局信息进行高层分析,使用基地址和偏移的组合来激进地表示一个结构体域成员以能更精确地区分结构体的不同域成员.文中还对原有类型推导规则做了重要改进,尽量避免在合并类型变量时造成的精度损失.为了保证新类型推导规则的正确性,方法将所有的结构体赋值操作转换成对每个结构体成员的赋值操作.大量实验数据表明,该方法分析精度显著高于以往方法而运行开销几乎相当.该方法还将域成员的激进表示集成至编译器的中间表示中以获得可移植性.

Pointer analysis is the basis of most other static program analyses for C programming language. The precision of pointer analysis is crucial to optimizing compilers and software productivity tools. Field-sensitivity is used to describe whether a pointer analysis needs to distinguish different field members. Field-insensitive pointer analysis considers all fields of one structural object as the same object. On the contrary, field-sensitive pointer analysis considers different fields as different objects. This paper proposes an aggressively field-sensitive unification-based pointer analysis. Different from existed methods, the method takes target machine architecture into con- sider in the phase of high-level analysis in order to precisely distinguish fields of structure objects. In the method, a field of a structural object is aggressively represented by a pair of offset from its base structure and size of its own data type. The original inference system is improved to avoid the loss of precision due to joining type variables. All structural memory operations are flattened to a series of scalar memory operations based on the target machine information to guarantee the correctness of type inference system. Lots of experiments indicate that the new method is more precise than the existed method while maintaining almost the same efficiency. Furthermore, the method is portable since the aggressive field representation have been implemented on the inter- mediate representation of the authors＇ compiler.