一种基于高阶函数摘要的依赖簇检测方法

A Dependence Clusters Detection Method Based on Higher-Order Function Summary

依赖簇是相互依赖的程序组件的最大集合,依赖簇中任意一点产生变动都会引起其他组件的连锁反应.在实际生产环境中,依赖簇检测对于软件理解、测试、维护具有非常重要的意义.传统的依赖簇检测方法基于系统依赖图(System Dependence Graph,SDG)实现过程间依赖关系的计算.但是SDG的构建过程比较复杂,时间空间的占用比较大.为提高依赖簇检测的效率并减少空间占用,本文提出了一种有效的轻量级依赖簇检测方法.该方法通过构建每个过程高阶函数形式的函数摘要,将形参和全局变量的数据依赖作为摘要参数,并用函数摘要的参数初始化过程内依赖信息.通过在调用点处对高阶函数形式的摘要进行实例化,即可将调用过程的依赖关系通过摘要参数进行传递,从而获取过程间的依赖信息.为了进一步提升检测效率,我们还提出了基于自适应计算的依赖簇检测优化策略,该策略可以减少因函数的递归调用产生的相关冗余计算.本文选取了不同规模不同领域的工程项目和基准测试集进行相关对比实验,结果表明:基于高阶函数的依赖簇检测方法相比系统依赖图的检测方法,能够提升2.689倍的分析效率并减少35.7%的空间占用;基于自适应计算的依赖簇检测优化策略在高阶函数方法的基础上能够减少56.7%的冗余计算,提升23.9%的分析效率.

Dependence clusters are the largest sets of interdependent program components,where any change in one point of the cluster can trigger a chain reaction in other components.In practical production environments,detecting depen⁃dence clusters is of great importance for software understanding,testing,and maintenance.Traditional dependence cluster de⁃tection methods rely on the system dependence graph(SDG)to calculate dependencies,However,constructing an SDG is a complex process that incurs significant time and space costs when analyzing large programs.In order to improve the efficien⁃cy of cluster detection,this paper proposes a light-weight and efficient dependence cluster detection method based on higherorder functions,which can avoid constructing SDG in the analysis.This method constructs a function summary in the form of a higher-order function for each procedure,where the data dependencies of formal parameters and global variables are used to initialize the dependence inside the procedure.The dependence cluster information between procedures can be obtained by in⁃stantiating the function summary and passing the dependence through summary parameters at the call site,which avoids the construction of an SDG.To further improve the analysis efficiency of the higher-order function-based detection method,we propose an optimization strategy based on adaptive computing,which significantly reduces the redundant calculations caused by the mutual recursive calls between functions.In the end,we select benchmark test sets with different scales and fields and conduct relevant experiments,which demonstrate that the proposed program dependence cluster detection method based on higher-order functions can improve analysis efficiency by 268.9%and reduce space usage by 35.7%compared with the detec⁃tion method based on SDG.The optimization strategy based on adaptive computing can reduce redundant calculations by 56.7%and improve analysis efficiency by 23.9%compared with the method based on higher-order functions.