[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article
Open access

Fast online pointer analysis

Published: 01 April 2007 Publication History

Abstract

Pointer analysis benefits many useful clients, such as compiler optimizations and bug finding tools. Unfortunately, common programming language features such as dynamic loading, reflection, and foreign language interfaces, make pointer analysis difficult. This article describes how to deal with these features by performing pointer analysis online during program execution. For example, dynamic loading may load code that is not available for analysis before the program starts. Only an online analysis can analyze such code, and thus support clients that optimize or find bugs in it. This article identifies all problems in performing Andersen's pointer analysis for the full Java language, presents solutions to these problems, and uses a full implementation of the solutions in a Java virtual machine for validation and performance evaluation. Our analysis is fast: On average over our benchmark suite, if the analysis recomputes points-to results upon each program change, most analysis pauses take under 0.1 seconds, and add up to 64.5 seconds.

References

[1]
Agrawal, G., Li, J., and Su, Q. 2002. Evaluating a demand driven technique for call graph construction. In Proceedings of the 11th International Conference on Compiler Construction (CC). Lecture Notes on Computer Science, vol. 2304. Springer Verlag, 29--45.
[2]
Alpern, B., Attanasio, C. R., Barton, J. J., Burke, M. G., Cheng, P., Choi, J.-D., Cocchi, A., Fink, S. J., Grove, D., Hind, M., Hummel, S. F., Lieber, D., Litvinov, V., Mergen, M. F., Ngo, T., Russell, J. R., Sarkar, V., Serrano, M. J., Shepherd, J. C., Smith, S. E., Sreedhar, V. C., Srinivasan, H., and Whaley, J. 2000. The Jalapeño virtual machine. IBM Syst. J. 39, 1 (Feb.), 211--238.
[3]
Andersen, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis, DIKU, University of Copenhagen. DIKU report 94/19. ftp://ftp.diku. dk/pub/diku/semantics/papers/D-203.dvi.Z.
[4]
Arnold, M., Fink, S., Grove, D., Hind, M., and Sweeney, P. F. 2000. Adaptive optimization in the Jalapeño JVM. ACM SIGPLAN Not. 35, 10 (Oct.), 47--65. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[5]
Arnold, M. and Ryder, B. G. 2002. Thin guards: A simple and effective technique for reducing the penalty of dynamic class loading. In Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP). Lecture Notes in Computer Science, vol. 2374. Springer Verlag.
[6]
Bacon, D. F. and Sweeney, P. F. 1996. Fast static analysis of C++ virtual function calls. ACM SIGPLAN Not. 31, 10 (Oct.), 324--341. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[7]
Berndl, M., Lhoták, O., Qian, F., Hendren, L., and Umanee, N. 2003. Points-to analysis using BDDs. ACM SIGPLAN Not. 38, 5 (May), 103--114. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[8]
Bogda, J. and Singh, A. 2001. Can a shape analysis work at run-time? In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM). 13--26.
[9]
Burke, M., Carini, P., Choi, J.-D., and Hind, M. 1994. Flow-Insensitive interprocedural alias analysis in the presence of pointers. In Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing (LCPC). Extended version published as Res. Rep. RC 19546, IBM T. J. Watson Research Center, September.
[10]
Burke, M. and Torczon, L. 1993. Interprocedural optimization: Eliminating unnecessary recompilation. ACM Trans. Program. Lang. Syst. 15, 3 (Jul.), 367--399.
[11]
Chatterjee, R., Ryder, B. G., and Landi, W. A. 1999. Relevant context inference. In Proceedings of the 26th Symposium on Principles of Programming Languages (POPL). 133--146.
[12]
Cheng, B.-C. and Hwu, W.-M. W. 2000. Modular interprocedural pointer analysis using access paths: Design, implementation, and evaluation. ACM SIGPLAN Not. 35, 5 (May), 57--69. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[13]
Choi, J.-D., Grove, D., Hind, M., and Sarkar, V. 1999. Efficient and precise modeling of exceptions for the analysis of Java programs. In Proceedings of the Workshop on Program Analysis for Software Tools and Engineering (PASTE). 21--31.
[14]
Choi, J.-D., Gupta, M., Serrano, M., Sreedhar, V. C., and Midkiff, S. 1999. Escape analysis for Java. ACM SIGPLAN Not. 34, 10 (Oct.), 1--19. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA).
[15]
Christensen, A. S., Møller, A., and Schwartzbach, M. I. 2003. Precise analysis of string expressions. In Proceedings of the 10th International Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 2694. Springer Verlag. 1--18.
[16]
Cierniak, M., Lueh, G.-Y., and Stichnoth, J. M. 2000. Practicing JUDO: Java under dynamic optimizations. ACM SIGPLAN Not. 35, 5 (May), 13--26. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[17]
Cooper, K. D., Kennedy, K., and Torczon, L. 1986. Interprocedural optimization: Eliminating unnecessary recompilation. ACM SIGPLAN Not. 21, 7 (Jul.), 58--67. In Proceedings of the Symposium on Compiler Construction (SCC).
[18]
Das, M. 2000. Unification-Based pointer analysis with directional assignments. ACM SIGPLAN Not. 35, 5 (May), 35--46. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[19]
Dean, J., Grove, D., and Chambers, C. 1995. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the 9th European Conference on Object-Oriented Programming (ECOOP). Lecture Notes in Computer Science, vol. 952. Springer Verlag. 77--101.
[20]
Detlefs, D. and Agesen, O. 1999. Inlining of virtual methods. In Proceedings of the 13th European Conference on Object-Oriented Programming (ECOOP). Lecture Notes in Computer Science, vol. 1628. Springer Verlag. 258--278.
[21]
Diwan, A., McKinley, K. S., and Moss, J. E. B. 2001. Using types to analyze and optimize object-oriented programs. ACM Trans. Program. Lang. Syst. 23, 1 (Jan.), 30--72.
[22]
Duesterwald, E., Gupta, R., and Soffa, M. L. 1997. A practical framework for demand-driven interprocedural data flow analysis. ACM Trans. Program. Lang. Syst. 19, 6 (Nov.), 992--1030.
[23]
Emami, M., Ghiya, R., and Hendren, L. J. 1994. Context-Sensitive interprocedural points-to analysis in the presence of function pointers. ACM SIGPLAN Not. 29, 6 (Jun.), 242--256. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[24]
Fähndrich, M., Foster, J. S., Su, Z., and Aiken, A. 1998. Partial online cycle elimination in inclusion constraint graphs. ACM SIGPLAN Not. 33, 5 (May), 85--96. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[25]
Fernández, M. F. 1995. Simple and effective link-time optimization of Modula-3 programs. ACM SIGPLAN Not. 30, 6 (Jun.), 103--115. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[26]
Fink, S. J. and Qian, F. 2003. Design, implementation and evaluation of adaptive recompilation with on-stack replacement. In Proceedings of the International Symposium on Code Generation and Optimization (CGO). 241--252.
[27]
Foster, J. S., Fähndrich, M., and Aiken, A. 1997. Flow-Insensitive points-to analysis with term and set constraints. Tech. Rep. UCB/CSD-97-964, University of California at Berkeley. August.
[28]
Ghiya, R. 1992. Interprocedural aliasing in the presence of function pointers. ACAPS Tech. Memo 62, McGill University. December.
[29]
Grove, D. 1998. Effective interprocedural optimization of object-oriented languages. Ph.D. thesis, University of Washington.
[30]
Grunwald, D. and Srinivasan, H. 1993. Data flow equations for explicitly parallel programs. In Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming.
[31]
Guyer, S. and Lin, C. 2003. Client-Driven pointer analysis. In Proceedings of the 10th International Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 2694. Springer Verlag. 214--236.
[32]
Hall, M. W., Mellor-Crummey, J. M., Carle, A., and Rodriguez, R. G. 1993. Fiat: A framework for interprocedural analysis and transformations. In Proceedings of the 6th Workshop on Languages and Compilers for Parallel Computing (LCPC). Lecture Notes in Computer Science, vol. 768. Springer Verlag. 522--545.
[33]
Harris, T. 1999. Early storage reclamation in a tracing garbage collector. ACM SIGPLAN Not. 34, 4 (Apr.), 46--53. In Proceedings of the International Symposium on Memory Management (ISMM).
[34]
Heintze, N. 1999. Analysis of large code bases: The compile-link-analyze model. Unpublished Rep. http://cm.bell-labs.com/cm/cs/who/nch/cla.ps.
[35]
Heintze, N. and Tardieu, O. 2001a. Demand-Driven pointer analysis. ACM SIGPLAN Not. 36, 5 (May), 24--34. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[36]
Heintze, N. and Tardieu, O. 2001b. Ultra-Fast aliasing analysis using CLA: A million lines of C code in a second. ACM SIGPLAN Not. 36, 5 (May), 254--263. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[37]
Hendren, L. 1990. Parallelizing programs with recursive data structures. Ph.D. thesis, Cornell University.
[38]
Hind, M. 2001. Pointer analysis: Haven't we solved this problem yet? In Workshop on Program Analysis for Software Tools and Engineering (PASTE). 54--61. Invited talk.
[39]
Hind, M. and Pioli, A. 2000. Which pointer analysis should I use? In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA). 113--123.
[40]
Hirzel, M., Diwan, A., and Hertz, M. 2003. Connectivity-Based garbage collection. ACM SIGPLAN Not. 38, 11 (Nov.), 359--373. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[41]
Hirzel, M., Diwan, A., and Hind, M. 2004. Pointer analysis in the pressence of dynamic class loading. In Proceedings of the 18th European Conference on Object-Oriented Programming (ECOOP). Lecture Notes in Computer Science, vol. 3086. Springer Verlag. 96--122.
[42]
Hirzel, M., Henkel, J., Diwan, A., and Hind, M. 2003. Understanding the connectivity of heap objects. ACM SIGPLAN Not. 38, 2s (Feb.), 143--156. In Proceedings of the International Symposium on Memory Management (ISMM).
[43]
Hölzle, U., Chambers, C., and Ungar, D. 1992. Debugging optimized code with dynamic deoptimization. ACM SIGPLAN Not. 27, 7 (Jul.), 32--43. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[44]
Hölzle, U. and Ungar, D. 1994. Optimizing dynamically-dispatched calls with run-time type feedback. ACM SIGPLAN Not. 29, 6 (Jun.), 326--336. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[45]
Hunt, G., Larus, J., Abadi, M., Aiken, M., Barham, P., Fähndrich, M., Hawblitzel, C., Hodson, O., Levi, S., Muprhy, N., Steensgaard, B., Tarditi, D., Wobber, T., and Zill, B. 2005. An overview of the Singularity project. Tech. Rep. MSR-TR-2005-135, Microsoft Research.
[46]
King, A. C. 2003. Removing synchronization (extended version). Tech. rep. 11-03, Computing Laboratory, University of Kent.
[47]
Kotzmann, T. and Mössenböck, H. 2005. Escape analysis in the context of dynamic compilation and deoptimization. In Virtual Execution Environments (VEE).
[48]
Larus, J. R. and Chandra, S. 1993. Using tracing and dynamic slicing to tune compilers. Tech. Rep. 1174. August.
[49]
Lattner, C. and Adve, V. 2003. Data structure analysis: An efficient context-sensitive heap analysis. Tech. Rep. UIUCDCS-R-2003-2340, Computer Science Department, University of Illinois at Urbana-Champaign. April.
[50]
Le, A., Lhoták, O., and Hendren, L. 2005. Using inter-procedural side-effect information in JIT optimizations. In Proceedings of the 14th International Conference on Compiler Construction (CC). Lecture Notes in Computer Science, vol. 3443. Springer Verlag. 287--304.
[51]
Lhoták, O. and Hendren, L. 2003. Scaling Java points-to analysis using SPARK. In Proceedings of the 12th International Conference on Compiler Construction (CC). Lecture Notes in Computer Science, vol. 2622. Springer Verlag. 153--169.
[52]
Liang, D. and Harrold, M. J. 1999. Efficient points-to analysis for whole-program analysis. In Proceedings of the 7th European Software Engineering Conference, and International Symposium on Foundations of Software Engineering (ESEC/FSE), O. Nierstraz and M. Lemoine, eds. Lecture Notes in Computer Science, vol. 1687. Springer Verlag. 199--215.
[53]
Liang, D., Pennings, M., and Harrold, M. J. 2001. Extending and evaluating flow-insensitive and context-insensitive points-to analyses for Java. In Proceedings of the Workshop on Program Analysis for Software Tools and Engineering (PASTE). 73--79.
[54]
Liang, D., Pennings, M., and Harrold, M. J. 2002. Evaluating the precision of static reference analysis using profiling. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA). 22--32.
[55]
Lindholm, T. and Yellin, F. 1999. The Java Virtual Machine Specification, 2nd ed. Addison-Wesley.
[56]
Livshits, B., Whaley, J., and Lam, M. S. 2005. Reflection analysis for Java. In Proceedings of the Asian Symposium on Programming Languages and Systems (APLAS).
[57]
Mock, M., Das, M., Chambers, C., and Eggers, S. J. 2001. Dynamic points-to sets: A comparison with static analyses and potential applications in program understanding and optimization. In Proceedings of the Workshop on Program Analysis for Software Tools and Engineering (PASTE). 66--72.
[58]
Paleczny, M., Vick, C., and Click, C. 2001. The Java Hotspot server compiler. In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM). 1--12.
[59]
Pechtchanski, I. and Sarkar, V. 2001. Dynamic optimistic interprocedural analysis: A framework and an application. ACM SIGPLAN Not. 36, 11 (Nov.), 195--210. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[60]
Plevyak, J. and Chien, A. A. 1994. Precise concrete type inference for object-oriented languages. ACM SIGPLAN Not. 29, 10 (Oct.), 324--324. In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA).
[61]
Qian, F. and Hendren, L. 2004. Towards dynamic interprocedural analysis in JVMs. In Proceedings of the 3rd Virtual Machine Research and Technology Symposium (VM). 139--150.
[62]
Qian, F. and Hendren, L. 2005. A study of type analysis for speculative method inlining in a JIT environment. In Proceedings of the 14th International Conference on Compiler Construction (CC). Lecture Notes in Computer Science, vol. 3443. Springer Verlag. 255--270.
[63]
Rountev, A. and Chandra, S. 2000. Off-Line variable substitution for scaling points-to analysis. ACM SIGPLAN Not. 35, 5 (May), 47--56. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[64]
Rountev, A., Milanova, A., and Ryder, B. G. 2001. Points-To analysis for Java using annotated constraints. ACM SIGPLAN Not. 36, 11 (Nov.), 43--55. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[65]
Ruf, E. 2000. Effective synchronization removal for Java. ACM SIGPLAN Not. 35, 5 (May), 208--218. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[66]
Ryder, B. G. 2003. Dimensions of precision in reference analysis for object-oriented programming languages. In Proceedings of the 12th International Conference on Compiler Construction (CC), G. Hedin, ed. Lecture Notes in Computer Science, vol. 2622. Springer Verlag. 126--137.
[67]
Sagiv, M., Reps, T., and Wilhelm, R. 1999. Parametric shape analysis via 3-valued logic. In Proceedings of the 26th Symposium on Principles of Programming Languages (POPL). 105--118.
[68]
Shapiro, M. and Horwitz, S. 1997. The effects of the precision of pointer analysis. In Proceedings of the 4th International Symposium on Static Analysis (SAS). Lecture Notes in Computer Science, vol. 1302. Springer Verlag. 16--34.
[69]
Sreedhar, V. C., Burke, M., and Choi, J.-D. 2000. A framework for interprocedural optimization in the presence of dynamic class loading. ACM SIGPLAN Not. 35, 5 (May), 196--207. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[70]
Sridharan, M. and Bodík, R. 2006. Refinement-Based context-sensitive points-to analysis for Java. In Proceedings of the Programming Language Design and Implementation (PLDI).
[71]
Steensgaard, B. 1996. Points-To analysis in almost linear time. In Proceedings of the 23rd Symposium on Principles of Programming Languages (POPL). 32--41.
[72]
Suganuma, T., Yasue, T., Kawahito, M., Komatsu, H., and Nakatani, T. 2001. A dynamic optimization framework for a Java just-in-time compiler. ACM SIGPLAN Not. 36, 11 (Nov.), 180--195. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[73]
Sundaresan, V., Hendren, L., Razafimahefa, C., Vallée-Rai, R., Lam, P., Gagnon, E., and Godin, C. 2000. Practical virtual method call resolution for Java. ACM SIGPLAN Not. 35, 10 (Oct.), 264--280. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[74]
Tip, F. and Palsberg, J. 2000. Scalable propagation-based call graph construction algorithms. ACM SIGPLAN Not. 35, 10 (Oct.), 281--293. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA).
[75]
Vallée-Rai, R., Gagnon, E., Hendren, L., Lam, P., Pominville, P., and Sundaresan, V. 2000. Optimizing Java bytecode using the Soot framework: Is it feasible? In Proceedings of the 9th International Conference on Compiler Construction (CC). Lecture Notes in Computer Science, vol. 1781. Springer Verlag. 18--34.
[76]
Vivien, F. and Rinard, M. 2001. Incrementalized pointer and escape analysis. ACM SIGPLAN Not. 36, 5 (May), 35--46. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI).
[77]
Whaley, J. and Lam, M. 2002. An efficient inclusion-based points-to analysis for strictly-typed languages. In Proceedings of the 9th International Symposium on Static Analysis (SAS). Lecture Notes in Computer Science, vol. 2477. Springer Verlag. 180--195.

Cited By

View all
  • (2024)Efficiently Trimming the Fat: Streamlining Software Dependencies with Java Reflection and Dependency AnalysisProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639123(1-12)Online publication date: 20-May-2024
  • (2023)Principled and practical static analysis for Python: Weakest precondition inference of hyperparameter constraintsSoftware: Practice and Experience10.1002/spe.327954:3(363-393)Online publication date: 22-Nov-2023
  • (2022)The raise of machine learning hyperparameter constraints in Python codeProceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534400(580-592)Online publication date: 18-Jul-2022
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems
ACM Transactions on Programming Languages and Systems  Volume 29, Issue 2
April 2007
327 pages
ISSN:0164-0925
EISSN:1558-4593
DOI:10.1145/1216374
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2007
Published in TOPLAS Volume 29, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Pointer analysis
  2. class loading
  3. native interface
  4. reflection

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)106
  • Downloads (Last 6 weeks)22
Reflects downloads up to 12 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Efficiently Trimming the Fat: Streamlining Software Dependencies with Java Reflection and Dependency AnalysisProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639123(1-12)Online publication date: 20-May-2024
  • (2023)Principled and practical static analysis for Python: Weakest precondition inference of hyperparameter constraintsSoftware: Practice and Experience10.1002/spe.327954:3(363-393)Online publication date: 22-Nov-2023
  • (2022)The raise of machine learning hyperparameter constraints in Python codeProceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534400(580-592)Online publication date: 18-Jul-2022
  • (2021)Taming ReflectionACM Transactions on Software Engineering and Methodology10.1145/344003330:3(1-36)Online publication date: 23-Apr-2021
  • (2020)Learning Unsupervised Knowledge-Enhanced Representations to Reduce the Semantic Gap in Information RetrievalACM Transactions on Information Systems10.1145/341799638:4(1-48)Online publication date: 11-Sep-2020
  • (2020)Pairwise Link Prediction Model for Out of Vocabulary Knowledge Base EntitiesACM Transactions on Information Systems10.1145/340611638:4(1-28)Online publication date: 2-Sep-2020
  • (2020)Embodiment, Presence, and Their IntersectionsACM Transactions on Human-Robot Interaction10.1145/33892109:4(1-19)Online publication date: 31-May-2020
  • (2020)Towards Effective Interface Designs for Collaborative HRI in ManufacturingACM Transactions on Human-Robot Interaction10.1145/33850099:4(1-55)Online publication date: 31-May-2020
  • (2020)Accurate Overlapping Method of Ultra-Long Interval Time-Lapse Images for World Heritage Site InvestigationJournal on Computing and Cultural Heritage 10.1145/337335713:2(1-18)Online publication date: 30-May-2020
  • (2020)Ambient Information Visualisation and Visitors’ Technology Acceptance of Mixed Reality in MuseumsJournal on Computing and Cultural Heritage 10.1145/335959013:2(1-22)Online publication date: 15-Jun-2020
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media