【作者】 孙强；

【导师】 赵建军；

【作者基本信息】 上海交通大学 ， 计算机软件与理论， 2013， 博士

【摘要】 程序指向分析是一种静态程序分析技术，它分析程序中指针类型的变量，并计算其运行时可能指向对象的集合。指向分析结果广泛应用于编译优化以及软件工程领域。流敏感和上下文敏感是提高程序指向分析精度的两个重要方面。前者计算控制流图上不同程序点中变量的指向关系，后者为同一个方法的变量在不同的调用上下文中计算出不同的指向关系。当前，程序指向分析技术面临两个重要的挑战。首先，我们需要协调分析精度和资源密集型计算之间的矛盾。流敏感的程序指向分析通常可以计算出高精度的程序指向关系，然而，这种分析依赖数据流迭代框架，导致它通常需要耗费大量计算资源。为此，我们引入概率和支持分析并行化，以有效提高程序指向分析的精度与效率。其次，我们需要扩展当前的上下文敏感的程序指向分析技术，使之能够充分适应新语言的特性。研究中我们针对新型语言，例如面向方面语言以及支持分区的全局地址空间（Partitioned Global Address Space，PGAS）模型的并发语言，研究在新型语言特征基础上的指向分析技术。本文主要贡献如下：提出了一种上下文非敏感流敏感的带概率的程序指向分析方法JPPA。JPPA能够静态地预测程序中某个指向关系在某个程序点成立的概率。JPPA的主要思想是通过在控制流图上进行带概率的数据流分析，从而计算出带概率的指向图。提出了并行的流敏感指向分析技术P S。我们首先建立流敏感需求驱动的指向分析方法S，它通过将流敏感性引入到指向依赖图和上下文无关语言（Context-Free Language，CFL）可达性中，从而支持查询指定变量指向关系。基于S，P S在指向依赖图上发起和处理一系列细粒度的查询以得到流敏感的指向关系。 P S使用Google的MapReduce框架并行处理查询，从而有效提高流敏感指向分析性能。扩展上下文敏感的程序指向分析技术，使之能够处理新型语言特征。论文提出了针对面向方面程序的上下文敏感的指向分析技术。该技术分别对基础代码和方面代码生成指向关系的约束和约束模版，并且通过迭代的方式来织入和求解约束，使分析跨越基础和方面代码的界限。此外，论文针对支持PGAS模型的并发程序提出了一个基于约束的地址分析方法，其首先定义了一个基于子集合包含关系的约束系统，以刻画对象、活动以及它们所在地址的约束关系。然后，我们采用活动敏感的上下文模型以进一步提高分析结果的精度。论文针对上述方法开发了配套工具，并且设计实验以评估其性能和精度。实验结果验证了论文所提出方法的有效性。特别需要指出的是，在8核的分布式系统中，论文所提出的并行流敏感指向分析技术能达到5.18×的最大平均加速比。更多还原

【Abstract】 Points-to analysis is a static code analysis technique that establishes the rela-tionships between variables of references and allocated objects. Flow-sensitivity andcontext-sensitivity are two major aspects of points-to analysis for improving the preci-sion of the analysis. While the fow-sensitive points-to analysis takes into account thecontrol fows inside a program or a method, and computes the solutions (i.e., points-to relations) for the program points on the control fow of each method, the context-sensitive points-to analysis distinguishes the diferent contexts in which a method isinvoked and then analyzes the method individually for each context.There are two challenges in the points-to analysis of programs. First, we shouldtake a tradeof between the analysis precision and resource-intensive computation.Flow-sensitivity is a major aspect of points-to analysis for improving the precision ofthe analysis. However, a fow-sensitive points-to analysis is resource-intensive in prac-tice in that it depends on the classic iterative datafow analysis framework. Therefore,we introduce the probability and parallelism into the points-to analysis to improve theprecision and performance of the analysis.Second,weshouldextendtheexistingcontext-sensitivepoints-toanalysistoadaptthe new language features. In the research, we study two new languages, which areaspect-orientedandPGAS-based(PartitionedGlobalAddressSpace)parallelprogram-ming language, to develop some extended analysis techniques. The extended tech-niques can take into account the new language features to achieve precise analysis re-sults.The paper makes the following contributions:We propose a context-insensitive and fow-sensitive probabilistic points-to anal- ysis JPPA for statically predicting the probability of points-to relations at all pro-gram points (i.e., points before or after statements) of a Java program. The keyidea of JPPA is to perform the probabilistic data fow analysis on a control fowgraph to compute the probabilistic points-to graph for each program point.We propose a parallel fow-sensitive points-to analysis Par Seeker. We frstdevelop Seeker which is a fow-sensitive approach to demand-driven points-toanalysis of Java program. Seeker introduces the fow sensitivity into a points-todependence graph and formulation of the context-free language reachability forsupporting points-to relation queries on the variables of interests. Based on thefoundation of Seeker, Par Seeker analyzes the points-to relations through pro-ducing and processing a set of fne-grained queries on a points-to dependencegraph. Par Seeker adopts the MapReduce framework proposed by Google toprocess a set of queries in parallel, which can improve the performance of fow-sensitive points-to analysis efciently.We extend the context-sensitive points-to analysis to adapt the new language fea-tures. We propose a context-sensitive points-to analysis technique for aspect-oriented programs. constraints and templates on the points-to relations for thebase code and the aspects, respectively, weaves and solves them in an iterativemanner in order to cross the boundary between the base code and the aspects.In addition, we propose a constraint-based locality analysis approach for PGASbased parallel programs. The approach uses a subset-based constraint systemto present the constraints on the objects, activities and their place. After that, itadopts the activity sensitive context model to improve the precision of the anal-ysis result.We have also developed tools for the approaches mentioned above, and design theexperiments to evaluate the precision and performance of the tools. The experimentsresults verify the efectiveness of our tools. Especially, Par Seeker achieves a speedupof up to5.18×on an8-core distributed system.更多还原