【作者】 李倩；

【导师】 赵建华；

【作者基本信息】 南京大学 ， 计算机软件与理论， 2012， 博士

【摘要】 指针指向分析的主要目的是静态地获取程序在运行时刻的指针指向信息。本文设计并实现了一种上下文敏感的基于约束的Java程序指向分析算法。在此基础上,本文提出了几项针对指向分析的优化技术,以此提高算法的效率和实用性。本文基于Andersen算法,设计了一种有效的上下文敏感的指针指向分析算法,该算法支持继承、字段对象等语言特性。不同对象的字段在算法中被分别处理,同时,算法对复合类型的对象实现了基于字段的处理。本文用有向图描述各个方法内部的指向关系,并以此为基础计算得到带上下文信息的全局指向图。为了提高算法的效率和可扩展性,本文首先引入了两种优化技术：结点拓扑排序和回路侦测与消除。结点间的拓扑排序的目标是降低分析过程中的迭代次数；另一个是在线的回路侦测与消除,它与拓扑排序过程同步实现。实验数据表明,本文提出的优化技术有效提高了算法的效率。此外,本文引入了指向副作用分析技术,这项技术可以进一步提高上下文敏感的指向分析算法的效率。指向副作用分析通过对局部指向图的分析找出程序中无指向副作用的方法集合。无指向副作用方法指的是那些不会改变其调用上下文中的指向关系的方法。在全局指向关系的分析过程中利用无指向副作用分析的结果可以避免计算一些无关的指向关系。实验数据表明,利用指向副作用分析结果可以进一步提高指向分析的效率。更多还原

【Abstract】 Points-to analysis mainly aims at getting the runtime points-to sets of program variables. This thesis designs and implements a context-sensitive constraint-based points-to analysis algorithm for Java programs. In addition, this thesis proposes several opitimizations which can be used to accerlerate the algorithm.This thesis describes the design and implementation of an efficient Andersen-style, context-sensitive points-to analysis algorithm for Java code. Our algorithm supports language features like inheritance, polymorphism, and field objects. We track the fields of individual objects separately and make the algorithm in field-sensitive style for aggregate objects. This algorithm first summarizes methods of the program under analysis using directed graphs. The main analysis algorithm uses these graphs to construct the main points-to graph.To improve the efficiency and scalability of the algorithm, this thesis employs two kinds of optimizations, nodes topology construction with concomitance on-line cycle detection and elimination. We perform cycle elimination on points-to graphs to reduce their sizes. Topological sort is performed simultaneously on the nodes of graph to speed up the transitive closure computationon in the main points-to graph. Experiment result shows that the efficiency of the algorithm is notably raised by using these two optimizations.This thesis also introduces a method which uses points-to side-effect(PSE) analysis to accelerate context sensitive points-to analysis. A PSE-free method has no mutation on points-to relation of its calling context. So it can be skipped during points-to analysis. Our method first finds PSE-free methods in the program by performing PSE analysis on the local points-to graphes of the methods. Based on these PSE analysis results, the main points-to analysis algorithm efficiently computes the points-to graph by skipping PSE-free methods. Experiment result shows that the efficiency of the algorithm can be further improved by using PSE analysis.更多还原