微信服务号

微信订阅号

2025年4月1日 18:32 星期二
首页 > 过刊浏览>2011年第22卷第6期 >1140-1154. DOI:10.3724/SP.J.1001.2011.04025
PDF HTML阅读 XML下载 导出引用 引用提醒
Java 指针指向分析优化
作者:
基金项目:

国家自然科学基金(90818022, 91018006, 61021062); 国家重点基础研究发展计划(973)(2009CB320702); 核高基项目(2009z01036-001-001-3)


Optimization of Points-to Analysis for Java
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [27]
    • |
  • 相似文献
    • | | |
  • 文章评论
    摘要:

    指针指向分析的主要目的是静态地获取程序在运行时刻的指针指向信息.基于Andersen 算法,设计了一种有效的、上下文敏感的指针指向分析算法,支持继承、字段对象等语言特性.不同对象的字段在算法中被分别处理,同时,算法对复合类型的对象实现了基于字段的处理.为了提高算法的效率和可扩展性,引入了两种优化方式:一种是结点间的拓扑排序以降低分析过程中的迭代次数;另一种是在线的环路侦测与消除,它与拓扑排序过程同步实现,有效地提高了处理效率.实验数据表明,该算法可以用来为较大规模的Java 代码生成精确的指向关系集合.

    Abstract:

    Points-to analysis mainly aims to attain the runtime points-to sets of program variables. This paper describes the design and implementation of an efficient Andersen-style, context-sensitive points-to analysis for Java code. The implementation supports language features such as inheritance, polymorphism, and field objects. The study tracks the fields of individual objects separately and makes the algorithm in field-sensitive style for aggregate objects. To improve the efficiency and scalability of the algorithm, this study employs two kinds of optimizations, nodes topology construction with concomitance on-line cycle detection and cycle elimination. Experiment results show that this algorithm can be used to compute precise points-to sets for large-scale Java programs.

    参考文献
    [1] Landi W, Ryder BG, Zhang S. Interprocedural modification side effect analysis with pointer aliasing. In: Proc. of the Conf. on Programming Language Design and Implementation (SIGPLAN’93). New York: ACM Press, 1993. 56?57. [doi: 10.1145/155090. 155096]
    [2] Ramalingam G. The undecidability of aliasing. ACM Trans. on Programming Languages and Systems, 1994,16(5):1467?1471. [doi: 10.1145/186025.186041]
    [3] Landi W. Undecidability of static analysis. ACM Letters on Programming Languages and Systems, 1992,1(4):323?337. [doi: 10.1145/161494.161501]
    [4] Ryder BG. Dimensions of precision in reference analysis of object-oriented programming languages. In: Hedin G, ed. Proc. of the CC 2003. LNCS 2622, Berlin, Heidelberg: Springer-Verlag, 2003. 126?137. [doi: 10.1007/3-540-36579-6_10]
    [5] Diwan A, Moss J.E.B, McKinley K. Simple and effective analysis of statically typed object-oriented programs. In: Proc. of the Conf. on Object-Oriented Programming Systems, Languages, and Applications. 1996. 292?305. [doi: 10.1145/236337.236367]
    [6] Bacon DF, Sweeney PF. Fast static analysis of C++ virtual function calls. In: Proc. of the Conf. on Object-Oriented Programming Systems, Languages, and Applications. New York: ACM Press, 1996. 324?341. [doi: 10.1145/236337.236371]
    [7] Whaley J, Monica S. Lam. Cloning-Based context-sensitive pointer alias analysis using binary decision diagrams. PLDI, 2004,39(6):131?144. [doi: 10.1145/996841.996859]
    [8] Lattner C, Lenharth A, Adve V. Making context-sensitive points-to analysis with heap cloning practical for the real world. In: Proc. of the 2007 ACM SIGPLAN Conf. on Programming Language Design and Implementation. 2007. [doi: 10.1145/1250734.1250766]
    [9] Pearce DJ, Kelly PHJ, Hankin C. Efficient field-sensitive pointer analysis for C. In ACM Workshop on Program Analysis for Software Tools and Engineering (PASTE), 2004. [doi: 10.1145/1290520.1290524]
    [10] Andersen LO. Program analysis and specialization for the C programming language [Ph.D. Thesis]. DIEM: University of Copenhagen, 1994.
    [11] Liang DL, Pennings M, Harrold MJ. Evaluating the impact of context-sensitivity on Andersen’s algorithm for Java programs. In: Proc. of the PASTE 2005. 2005. [doi: 10.1145/1108792.1108797]
    [12] Liang DL, Pennings M, Harrold MJ. Extending and evaluating flow-insensitive and context-insensitive points-to analyses for Java. In: Proc. of the Workshop on Program Analysis for Software Tools and Engineering. 2001. 73?79. [doi: 10.1145/379605.379676]
    [13] Heintze N, Tardieu O. Ultra-Fast aliasing analysis using CLA: A million lines of C code. In: Proc. of the Conf. on Programming Language Design and Implementation (PLDI). 2001. 146?161. [doi: 10.1145/378795.378855]
    [14] Whaley J, Lam MS. An efficient inclusion-based points-to analysis for strictly-typed languages. In: Proc. of the Static Analysis Symp. 2002. 180?195. [doi: 10.1007/3-540-45789-5_15]
    [15] Berndl M, Lhot′ak O, Qian F, Hendren L, Umanee N. Points to analysis using BDDs. In: Proc. of the Conf. on Programming Language Design and Implementation. New York: ACM Press, 2003. 103?114.
    [16] Sridharan M, Gopan D, Shan LX, Bodik R. Demand-Driven points-to analysis for Java. In: Proc. of the 20th Annual ACM SIGPLAN Conf. on Object-Oriented Programming, Systems, Languages, and Applications. 2005. [doi: 10.1145/1094811.1094817]
    [17] Rountev A, Milanova A, Ryder BG. Points-to analysis for Java using annotated constraints. In: Proc. of the Conf. on Object-Oriented Programming Systems, Languages, and Applications. 2001. 43?55. [doi: 10.1145/504282.504286]
    [18] Steensgaards B. Points-to analysis in almost linear time. In: Proc. of the ACM Symp. on Principles of Programming Languages (POPL). New York: ACM Press, 1996. 32?41. [doi: 10.1145/237721.237727]
    [19] Das M. Unification-Based pointer analysis with directional assignments. In: Proc. of the ACM Conf. on Programming Language Design and Implementation (PLDI). New York: ACM Press, 2000. 35?46. [doi: 10.1145/349299.349309]
    [20] Kahlon V. Bootstrapping: A technique for scalable flow and context-sensitive pointer alias analysis. In: Proc. of the PLDI 2008. New York: ACM Press, 2008. [doi: 10.1145/1375581.1375613]
    [21] Hind M, Pioli A. Which pointer analysis should I use? In: Proc. of the International Symposium on Software Testing and Analysis (ISSTA). 2000. 113?123. [doi: 10.1145/347324.348916]
    [22] Lhoták O, Hendren L. Context-Sensitive points-to analysis: Is it worth it? In: Proc. of the Int’l Conf. on Compiler Construction. LNCS 3923, 2006. 47?64. [doi: 10.1007/11688839_5]
    [23] Rountev A, Chandra S. Off-Line variable substitution for scaling points-to analysis. In: Proc. of the 2000 Conf. on Programming Language Design and Implementation. 2000. [doi: 10.1145/349299.349310]
    [24] F?ehndrich M, Foster JS, Su Z, Aiken A. Partial online cycle elimination in inclusion constraint graphs. In: Proc. of the Programming Language Design and Implementation (PLDI). 1998. 85?96. [doi: 10.1145/277650.277667]
    [25] Su ZD, F?hndrich M, Aiken A. Projection merging: Reducing redundancies in inclusion constraint graphs. In: Proc. of the 27th Annual ACM SIGPLANSIGACT Symp. on Principles of Programming Languages (POPL). 2000. [doi: 10.1145/325694.325706]
    [26] Hardekopf B, Lin C. The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code. In: Proc. of the Programming Language Design and Implementation (PLDI). 2007. [doi: 10.1145/1250734.1250767]
    [27] Mendez-Lojo M, Mathew A, Pingali K. Parallel inclusion-based points-to analysis. In: Proc. of the OOPSLA/SPLASH. 2010. [doi: 10.1145/1869459.1869495]
    相似文献
    引证文献
引用本文

李倩,汤恩义,戴雪峰,王林章,赵建华. Java 指针指向分析优化.软件学报,2011,22(6):1140-1154

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2010-07-10
  • 最后修改日期:2011-03-29
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号