Page 32 - 《软件学报》2024年第6期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2024,35(6):2608−2630 [doi: 10.13328/j.cnki.jos.007100] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
DDoop: 基于差分式 Datalog 求解的增量指针分析框架

沈天琪 1,2 , 王熙灶 1,2 , 宾向荣 1,2 , 卜 磊 1,3

(计算机软件新技术全国重点实验室 (南京大学), 江苏 南京 210023)
1
2
(南京大学 计算机科学与技术系, 江苏 南京 210023)
3
(南京大学 软件学院, 江苏 南京 210023)
通信作者: 卜磊, E-mail: bulei@nju.edu.cn

摘 要: 指针分析是对软件进行编译优化、错误检测的核心基础技术之一. 现有经典指针分析框架, 如 Doop, 会将
待分析程序和分析算法转化成 Datalog 评估问题并进行求解, 如程序规模较大, 单次求解分析时间开销较大. 在程
序频繁变更发布的情况下, 相关程序分析的开销更是难以负担. 近年来, 增量分析作为一种在代码频繁变更场景下
有效复用已有分析结果提升分析效率的技术受到了越来越多的关注. 然而, 目前的增量指针分析技术通常针对特
定算法设计, 支持的指针分析选项有限, 其可用性也受到较大限制. 针对上述问题, 设计并实现一种基于差分式
Datalog 求解的增量指针分析框架 DDoop (Differential Doop). DDoop 实现增量输入事实生成技术与增量分析规则
自动化重写技术, 将多版本程序增量分析问题表达为差分 Datalog 评估问题, 从而可以充分利用成熟的差分式
Datalog 求解引擎, 如 DDlog, 来实现端到端的增量指针分析, 并最大化兼容复用 Doop 中已有的指针分析实现, 提
供透明的增量化支持. 在广泛应用的真实世界程序上对 DDoop 进行实验评估, 实验结果显示 DDoop 相较于非增
量的 Doop 框架具有显著的性能优势, 同时高度兼容 Doop 中已有的各种指针分析规则.
关键词: 指针分析; 增量分析; Datalog 引擎; 增量计算; 差分式 Datalog
中图法分类号: TP314

中文引用格式: 沈天琪, 王熙灶, 宾向荣, 卜磊. DDoop: 基于差分式Datalog求解的增量指针分析框架. 软件学报, 2024, 35(6):
2608–2630. http://www.jos.org.cn/1000-9825/7100.htm
英文引用格式: Shen TQ, Wang XZ, Bin XR, Bu L. DDoop: Incremental Pointer Analysis Framework Based on Differential Datalog
Evaluation. Ruan Jian Xue Bao/Journal of Software, 2024, 35(6): 2608–2630 (in Chinese). http://www.jos.org.cn/1000-9825/7100.htm

DDoop: Incremental Pointer Analysis Framework Based on Differential Datalog Evaluation
1,2
1,2
1,2
SHEN Tian-Qi , WANG Xi-Zao , BIN Xiang-Rong , BU Lei 1,3
1
(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China)
2
(Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China)
3
(Software Institute, Nanjing University, Nanjing 210023, China)
Abstract: Pointer analysis is a core and fundamental technology for software compiler optimization and bug detection. Existing classic
pointer analysis frameworks such as Doop will transform the programs to be analyzed and analysis algorithms into Datalog evaluation
problems like too large program size and solve them. As a result, the analysis time overhead of a single solution can be high, and the
program analysis overhead can hardly be afforded especially in situations where programs are frequently changed and released. In recent
years, as a technology that effectively reemploys existing analysis results and improves analysis efficiency under frequent code changes,
incremental analysis has caught increasing attention. However, since current incremental pointer analysis techniques are often designed for

* 基金项目: 国家自然科学基金 (62232008, 62172200); 江苏省前沿引领技术基础研究专项 (BK20202001); 中央高校基本科研业务费专项
资金 (020214380101)
本文由“编译技术与编译器设计”专题特约编辑冯晓兵研究员、郝丹教授、高耀清博士、左志强副教授推荐.
收稿时间: 2023-09-11; 修改时间: 2023-10-30; 采用时间: 2023-12-14; jos 在线出版时间: 2024-01-05
CNKI 网络首发时间: 2024-03-29