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

Optimization Technique for Interprocedual Analysis Using Function Inlining in Abstract Interpretation

作　　者：陈涛清 范广生 尹帮虎 陈立前[1] 王戟[1,3] CHEN Tao-Qing;FAN Guang-Sheng;YIN Bang-Hu;CHEN Li-Qian;WANG Ji(College of Computer Science and Technology,National University of Defense Technology,Changsha 410073,China;College of Systems Engineering,National University of Defense Technology,Changsha 410073,China;State Key Laboratory for High Performance Computing(National University of Defense Technology),Changsha 410073,China)

机构地区：[1]国防科技大学计算机学院,湖南长沙410073 [2]国防科技大学系统工程学院,湖南长沙410073 [3]高性能计算国家重点实验室(国防科技大学),湖南长沙410073

出　　处：《软件学报》2022年第8期2964-2979,共16页Journal of Software

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

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

关 键 词：过程间分析 抽象解释 函数内联 变量消除 降维 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]