基于指向更新的优先权指针分析算法  

Prioritizing Pointer Analysis Algorithm Based on Points-to Updating

作　　者：刘鹏[1] 赵荣彩[1] 庞建民[1] 姚远[1] 

机构地区：[1]解放军信息工程大学,河南郑州450002

出　　处：《软件学报》2014年第11期2486-2498,共13页Journal of Software

基　　金：国家高技术研究发展计划(863)(2009AA012201);"核高基"国家科技重大专项(2009ZX01036-001-001-2)

摘　　要：指针分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础.在基于包含的指针分析算法研究的基础上,对Narse优先权约束评估算法中存在的冗余约束评估和优先权评估模型计算开销较大的问题进行分析,以指针的指向集更新信息确定约束评估的候选集,提出了基于指向更新的约束评估算法.采用约束语句间的解,引用依赖和标量依赖构建约束依赖图,通过依赖关系确定约束评估的优先权,提出了基于约束依赖图的优先权算法,简化了既有算法中复杂的优先权评估模型,进一步给出了优化后算法的整体框架.在基准测试集SPEC2000/SPEC 2006上进行实验,其结果表明,该算法与Narse优先权算法相比,在时间开销和存储开销上都有明显的性能提升.Pointer analysis is a key technology in data flow analysis, and the result of pointer analysis is the basis of compiler optimization and program transformation. Based on the inclusion-based pointer analysis algorithm research, this paper analyzes the problems of redundant constraints evaluation and computational overhead of priority evaluation model in Narse priority constraints evaluation algorithm. Candidate set of constraint evaluation is determined by points-to set updating information of pointers, and the prioritizing pointer analysis algorithm based on points-to updating is presented. Constraint dependency graph is built by pointer dereferance dependence and pointer scalar dependence in constraint statements, and priority of constraint evaluation is determined by the dependencies. Prioritizing algorithm based on constraint dependency graph is presented to simplify the complex priority evaluation model in Narse algorithm, and the overall framework of the optimized algorithm is provided. The experimental results on SPEC 2000/SPEC 2006 benchmark show that the algorithm has a significant performance boost on the time overhead and storage overhead compared with Narse priority algorithm.

关 键 词：指针分析 数据流分析 指向集 流不敏感 

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