java指向的分析性能优化

《java指向的分析性能优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江大学硕士学位论文摘要基于包含的指向分析由于在分析精度上和时间开销上具有良好的平衡，得到了最为深入的研究，但是它的时间复杂度为o(n3)，11为指向分析的变量总数。本文利用投机并行优化了约束求解过程，利用基于工作集的等价变量合并策略优化了约束简化过程，在保证分析精度的同时有效地降低了时间开销。具体来说，论文包含以下内容：(1)对约束求解过程实现了并行化。多核的出现为程序分析问题提供了并行化的解决思路，然而指向分析由于约束求解过程存在高度的数据依赖性，在并行实现上进展缓慢。本文把基于包含的Java指向分析形式化为图问题，把约束求解过程转换为图改写操作，结合并行计

2、算中对非规整程序投机执行的思想，利用Galois系统实现了并行化。(2)为约束简化过程设计了新的等价变量合并策略。本文对Java指向分析的约束简化过程进行了细粒度的分析和测试，发现已有的等价变量合并算法效率低下，用于并行化的指向分析会制约整体性能的提高。因此，针对Copy约束构成的强连通分量引起的等价变量，本文设计了一种基于工作集的合并算法，通过只迭代满足合并条件的指向变量，减少了对所有变量的遍历次数。(3)对以上优化技术在Soot框架上进行了高效的实现，使用通用基准程序进行了测试和比较。实验结果表明，相比于目前性能最优的Java指向分析框架Spark，本文的方

3、法取得了2．2倍的性能提升。关键词：Java，Galois系统，指向分析，并行化，图改写浙江大学硕士学位论文AbstractDuetogoodbalancebetweenprecisionandtimeoverhead，inclusion—basedpoints-toanalysishasbeenstudiedmostprofoundlyamongmanypoints-toanalysisalgorithms，butsuffersfromhightimecomplexity,whichisproportionaltothecubeoftheamountofvar

4、iablesinvolvedinanalysis．Inthispaper,wereduceitstimeoverheadswithtwostrategies：optimisticparallelizationforconstraintsolvingandwork-listbasedmergingalgorithmforequivalentvariablesinconstraintsimplification．Specifically,itcomeswiththefollowingapescts：First，weparallelizeconstraintsolvi

5、ngwithGaloisSystem．Recently,increasedcomputingpowerprovidedbymultiplecorescanbeutilizedtodevelopparallelizedsolutions；however,itisstillininfancyforpoints—toanalysisbecauseofheavydatadependenciesexistinginthisprobknn．Weformalizeinclusion—basedpoints—toanalysisforJavaasagraphproblem，tr

6、ansformconstraintsolvingintographrewriting，andparallelizeitbyofoptimisticparallelizationforirregularprogramswithGaloissystem．Second，wedevelopanewalgorithmformergingequivalentvariables．Weconductafine-grainedtestonconstraintsimplification，findingthatexistingalgorithmsformergingequivale

7、ntvariablesareinefficient，andwouldlimitoverallperformanceiftheyareappliedinparallelizedpoints—toanalysis．So，wedeviseaworklist-basedalgorithmformergingequivalentvariablesonstronglyconnectedcomponentsformedbyCopyconstraints，reducingiterationsonallvariables．Atlast，weimplementandevaluate

8、themonSootfr