一句话：提出增量且并行的指针分析算法 IPA，避免冗余计算与图可达性分析，在保持精度同时实现大幅加速。
指针分析是多数过程间程序分析的核心，但将其扩展到大型程序非常困难。本文研究增量指针分析，提出在代码插入、删除和修改时增量计算指向信息的新算法 IPA。基于对增量指针分析的新观察，IPA 避免冗余计算和昂贵的图可达性分析，并保持与对应全程序穷尽分析相同的精度；同时在每次不动点迭代内实现并行。作者基于 WALA 框架为 Java 实现 IPA，并在真实大型复杂应用上广泛评测。结果表明，IPA 较现有增量算法加速超过 200 倍，比全程序指针分析快 2 到 5 个数量级，还将增量数据竞争检测器的性能提升数个数量级；其实现已开源并被 WALA 采用。
Pointer analysis is at the heart of most interprocedural program analyses. However, scaling pointer analysis to large programs is extremely challenging. In this article, we study incremental pointer analysis and present a new algorithm for computing the points-to information incrementally (i.e., upon code insertion, deletion, and modification). Underpinned by new observations of incremental pointer analysis, our algorithm significantly advances the state of the art in that it avoids redundant computations and the expensive graph reachability analysis, and preserves precision as the corresponding whole program exhaustive analysis. Moreover, it is parallel within each iteration of fixed-point computation. We have implemented our algorithm, IPA, for Java based on the WALA framework and evaluated its performance extensively on real-world large, complex applications. Experimental results show that IPA achieves more than 200X speedups over existing incremental algorithms, two to five orders of magnitude faster than whole program pointer analysis, and also improves the performance of an incremental data race detector by orders of magnitude. Our IPA implementation is open source and has been adopted by WALA.
DOI 原文 ·
@article{paperbot716,
title = {Rethinking Incremental and Parallel Pointer Analysis},
author = {Bozhen Liu and Jeff Huang and Lawrence Rauchwerger},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {41},
number = {1},
year = {2019},
doi = {10.1145/3293606}
}