Java指向分析性能优化

摘要

基于包含的指向分析由于在分析精度上和时间开销上具有良好的平衡，得到了最为深入的研究，但是它的时间复杂度为O(n3)，n为指向分析的变量总数。本文利用投机并行优化了约束求解过程，利用基于工作集的等价变量合并策略优化了约束简化过程，在保证分析精度的同时有效地降低了时间开销。具体来说，论文包含以下内容:
　　(1)对约束求解过程实现了并行化。多核的出现为程序分析问题提供了并行化的解决思路，然而指向分析由于约束求解过程存在高度的数据依赖性，在并行实现上进展缓慢。本文把基于包含的Java指向分析形式化为图问题，把约束求解过程转换为图改写操作，结合并行计算中对非规整程序投机执行的思想，利用Galois系统实现了并行化。
　　(2)为约束简化过程设计了新的等价变量合并策略。本文对Java指向分析的约束简化过程进行了细粒度的分析和测试，发现已有的等价变量合并算法效率低下，用于并行化的指向分析会制约整体性能的提高。因此，针对Copy约束构成的强连通分量引起的等价变量，本文设计了一种基于工作集的合并算法，通过只迭代满足合并条件的指向变量，减少了对所有变量的遍历次数。
　　(3)对以上优化技术在Soot框架上进行了高效的实现，使用通用基准程序进行了测试和比较。实验结果表明，相比于目前性能最优的Java指向分析框架Spark，本文的方法取得了2.2倍的性能提升。

目录

摘要

图目录

表目录

第1章 绪论

1．1 课题背景

1．2 国内外研究现状

1．3 本文主要工作

1．4 论文组织结构

1．5 本章小结‘

第2章 Java指向分析基础

2．1 指向分析的定义

2．2 指向分析的维度

2．2．1 流敏感性

2．2．2 上下文敏感性

2．2．3 字段敏感性

2．3 指向分析的过程

2．3．1 约束生成

2．3．2 约束简化

2．3．3 约束求解

2．4 指向集传播策略

2．4．1 基于迭代的传播

2．4．2 基于工作集的传播

2．4．3 基于别名关系的传播

2．5 指向集表示方法

2．6 本章小结

第3章 基于图改写的约束求解

3．1 约束图建模

3．2 约束图改写

3．2．1 改写规则

3．2．2 改写过程

3．2．3 可并行性

3．3 Galois系统

3．3．1 基本原理

3．3．2 并行模型

3．4 图改写并行化

3．4．1 基本思想

3．4．2 优化策略

3．4．3 同步控制

3．4．4 算法框架

3．5 本章小结

第4章 基于工作集的等价变量合并

4．1 等价变量来源

4．1．1 强连通分量

4．1．2 单入口子图

4．2 基于迭代的合并算法

4．2．1 基本思想

4．2．2 算法框架

4．2．3 算法分析

4．3 基于工作集的合并算法

4．3．1 基本思想

4．3．2 算法框架

4．3．3 算法分析

4．4 本章小结

第5章 实验与数据分析

5．1 实验方案

5．1．1 实验设计

5．1．2 环境配置

5．1．3 测试基准

5．2 测试结果

5．2．1 离线开销

5．2．2 在线开销

5．2．3 整体开销

5．2．4 内存使用

5．3 本章小结

第6章 总结与展望

参考文献

攻读硕士学位期间主要的研究成果

致谢