流敏感按需指针别名分析算法

Research on Flow Sensitive Demand Driven Alias Analysis

为了提高交互环境下指针别名查询的响应效率,近期研究提出通过只分析与目标相关指针的按需分析策略来降低浪费在与目标无关的指针分析的额外开销.典型的代表是基于上下文无关文法的按需别名分析算法.但是,该算法的精度只局限于控制流不敏感.控制流不敏感的别名关系将约束上层分析的精度.针对该不足,提出了具有流敏感精度的按需别名分析算法.首先采用不完全静态单赋值语句形式来区分指针变量赋值实例,然后通过层次线性化编码方法来表达控制流图中的流敏感信息以构建赋值流图,最后将别名关系查询问题转换为在赋值流图上搜索目标结点间在控制流可达条件下赋值路径的可达性问题,进而实现流敏感的按需别名分析.实验表明,与流不敏感的按需别名分析相比,该方法可以在保证查询效率的前提下,有效提高按需别名分析的精度.

In order to improve the response efficiency of pointer alias queries in the interactive environment,researches are interested in the demand driven strategy to reduce the cost for analyzing the unrelated pointer variables with respect to the objectives.The demand driven alias analysis based on the context free grammar has been proposed.However,its precision is only limited to the flowinsensitivity.The flow-insensitivity pointer alias restricts the precision of overlying analysis,so the bug detection results in more false alarms than the one with flow-sensitive alias analysis.In this paper,we propose a demand driven pointer alias analysis based on the graph reachability and the context free grammar to provide the flow sensitive precision,which has tolerable additional overhead comparing with the flow-insensitive alias analysis.First the updates of pointer variables are discriminated by the partial single static assignment to filter out the unrelated pointer variables as early as possible.Then the sequence of control flow along these assignments is expressed in the form of level linearization code,which is used to construct the assignment flow graph.Finally,the query of alias in demand driven is formalized as the search of reachability of target nodes in the assignment flow graph to achieve the precision of flow sensitivity.The experiments demonstrate that this presented method can improve the flow sensitivity the precision of alias analysis in demand driven with overhead tolerable.