微信服务号

微信订阅号

2025-4-5- 10
Home > Archive>Volume 22, Issue 6, 2011 >1140-1154. DOI:10.3724/SP.J.1001.2011.04025
PDF HTML XML Export Cite reminder
Optimization of Points-to Analysis for Java
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [27]
    • |
  • Related
    • | | |
  • Comments
    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.

    Reference
    [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]
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:8944
  • PDF: 10258
  • HTML: 0
  • Cited by: 0
History
  • Received:July 10,2010
  • Revised:March 29,2011
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033139Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063