基于抽象解释的函数内联过程间分析优化方法
作者:
作者单位:

作者简介:

陈涛清(1997-),男,硕士生,主要研究领域为程序分析;
陈立前(1982-),男,博士,副教授,CCF高级会员,主要研究领域为程序分析与验证,抽象解释;
范广生(1997-),男,博士生,主要研究领域为程序分析与验证,抽象解释;
王戟(1969-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为软件方法学,软件分析与验证,并行与分布计算;
尹帮虎(1989-),男,博士,讲师,主要研究领域为程序分析与验证,系统建模与仿真.

通讯作者:

尹帮虎,E-mail:bhyin@nudt.edu.cn;王戟,E-mail:wj@nudt.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(62032024,61872445,62102432);湖南省自然科学基金(2021JJ40697)


Optimization Technique for Interprocedual Analysis Using Function Inlining in Abstract Interpretation
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    分析实际程序时往往需要分析程序中函数的调用,一般使用过程间分析来实现全程序分析.函数内联是一种最为精确、易于实现的过程间分析方法.通过函数内联,可以使得已有过程内分析方法和工具支持包含函数调用的程序的分析.但是函数内联后代码的规模急剧增加,同时将产生大量中间变量,增加程序分析的变量维度,导致程序分析过程时空开销大大增加.考虑基于抽象解释框架下函数内联过程间分析的一些不足,并提出了相应的优化方法.基于抽象解释的程序分析关注自动推导程序变量之间的不变式约束关系,因此程序变量构成的程序环境大小(即各程序点处须考虑的相关变量集合)对分析的时空开销具有重要影响.为了减少函数内联后程序分析的开销,提出了面向内联函数块的程序环境降维优化方法.该方法针对内联函数后的程序代码,分析确定不同程序点处需维护的程序环境(即相关变量集合),而不是所有程序点共享同一全局程序环境,从而实现程序状态的降维.详细描述了基于该方法所实现的工具DRIP (dimension reduction for analyzing function inlined program)的架构、模块及算法细节.并在WCET Benchmarks测试集开展了分析实验.实验结果表明:DRIP在变量消除上取得的效果良好,甚至在某些测试集上能减少一半以上的变量,并在一定程度上降低了分析过程的时空开销.

    Abstract:

    When analyzing real-world programs, it is often necessary to analyze the function calls in the program, and interprocedural analysis is generally used to achieve full program analysis. Function inlining is one of the most accurate and easily achievable methods for interprocedural analysis. Function inlining allows existing intraprocedural analysis methods and tools to support the analysis of programs that contain function calls. However, the size of the code increases dramatically after function inlining, and a large number of intermediate variables will be generated, which increases the variable dimension of program analysis and causes the process of program analysis to consume a lot of memory and time. This study considers some shortcomings of interprocedural analysis of function inlining based on the abstract interpretation framework and proposes a corresponding optimization method. Program analysis based on abstract interpretation is concerned with automatically deriving invariant constraint relations among program variables, so the size of the program environment constituted by program variables (i.e., the set of relevant variables to be considered at each program point) has an important impact on the time and space overhead of the analysis. In order to reduce the overhead of program analysis after function inlining, this study proposes a program environment reduction optimization method for inline function blocks. The method analyzes the program code after inlining functions to determine the program environment (i.e., set of related variables) to be maintained at different program points, instead of sharing the same global program environment at all program points, so as to realize the dimensionality reduction of the program state. The architecture, modules, and algorithm details of the tool DRIP (dimension reduction for analyzing function inlined program) implemented based on this method are described in detail. The results show that DRIP achieves sound results in variable elimination, even reducing more than half of the variables in some test suites, and the time and space spent is also reduced to a certain extent.

    参考文献
    相似文献
    引证文献
引用本文

陈涛清,范广生,尹帮虎,陈立前,王戟.基于抽象解释的函数内联过程间分析优化方法.软件学报,2022,33(8):2964-2979

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-09-06
  • 最后修改日期:2021-10-14
  • 录用日期:
  • 在线发布日期: 2022-01-28
  • 出版日期: 2022-08-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号