论文部分内容阅读
程序指向分析是一种静态程序分析技术,它分析程序中指针类型的变量,并计算其运行时可能指向对象的集合。指向分析结果广泛应用于编译优化以及软件工程领域。流敏感和上下文敏感是提高程序指向分析精度的两个重要方面。前者计算控制流图上不同程序点中变量的指向关系,后者为同一个方法的变量在不同的调用上下文中计算出不同的指向关系。当前,程序指向分析技术面临两个重要的挑战。首先,我们需要协调分析精度和资源密集型计算之间的矛盾。流敏感的程序指向分析通常可以计算出高精度的程序指向关系,然而,这种分析依赖数据流迭代框架,导致它通常需要耗费大量计算资源。为此,我们引入概率和支持分析并行化,以有效提高程序指向分析的精度与效率。其次,我们需要扩展当前的上下文敏感的程序指向分析技术,使之能够充分适应新语言的特性。研究中我们针对新型语言,例如面向方面语言以及支持分区的全局地址空间(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×的最大平均加速比。