Fast online pointer analysis

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: Gagan Agrawal , Jinqian Li , Qi Su, Evaluating a Demand Driven Technique for Call Graph Construction, Proceedings of the 11th International Conference on Compiler Construction, p.29-45, April 08-12, 2002
• 2: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 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: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, ACM SIGPLAN Notices, v.35 n.10, p.47-65, Oct. 2000
• 5: Matthew Arnold , Barbara G. Ryder, Thin Guards: A Simple and Effective Technique for Reducing the Penalty of Dynamic Class Loading, Proceedings of the 16th European Conference on Object-Oriented Programming, p.498-524, June 10-14, 2002
• 6: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, ACM SIGPLAN Notices, v.31 n.10, p.324-341, Oct. 1996
• 7: Marc Berndl , Ondrej Lhoták , Feng Qian , Laurie Hendren , Navindra Umanee, Points-to analysis using BDDs, ACM SIGPLAN Notices, v.38 n.5, May 2003
• 8: Jeff Bogda , Ambuj Singh, Can a shape analysis work at run-time?, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.2-2, April 23-24, 2001, Monterey, California
• 9: Michael G. Burke , Paul R. Carini , Jong-Deok Choi , Michael Hind, Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.234-250, August 08-10, 1994
• 10: Michael Burke , Linda Torczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.367-399, July 1993 [doi>10.1145/169683.169678]
• 11: Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292554]
• 12: Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, ACM SIGPLAN Notices, v.35 n.5, p.57-69, May 2000
• 13: Jong-Deok Choi , David Grove , Michael Hind , Vivek Sarkar, Efficient and precise modeling of exceptions for the analysis of Java programs, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.21-31, September 06-06, 1999, Toulouse, France
• 14: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, ACM SIGPLAN Notices, v.34 n.10, p.1-19, Oct. 1999
• 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: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, ACM SIGPLAN Notices, v.35 n.5, p.13-26, May 2000
• 17: Keith D. Cooper , Ken Kennedy , Linda Lorczon, Interprocedural optimization: eliminating unnecessary recompilation, ACM SIGPLAN Notices, v.21 n.7, p.58-67, July 1986
• 18: Manuvir Das, Unification-based pointer analysis with directional assignments, ACM SIGPLAN Notices, v.35 n.5, p.35-46, May 2000
• 19: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 20: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 21: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001 [doi>10.1145/383721.383732]
• 22: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical framework for demand-driven interprocedural data flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.992-1030, Nov. 1997 [doi>10.1145/267959.269970]
• 23: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, ACM SIGPLAN Notices, v.29 n.6, p.242-256, June 1994
• 24: Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su , Alexander Aiken, Partial online cycle elimination in inclusion constraint graphs, ACM SIGPLAN Notices, v.33 n.5, p.85-96, May 1998
• 25: Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, ACM SIGPLAN Notices, v.30 n.6, p.103-115, June 1995
• 26: Stephen J. Fink , Feng Qian, Design, implementation and evaluation of adaptive recompilation with on-stack replacement, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 27: Jeffrey S. Foster , Manuel Fahndrich , Alexander Aiken, Flow-Insensitive Points-to Analysis with Term and Set Constraints, University of California at Berkeley, Berkeley, CA, 1997
• 28: Ghiya, R. 1992. Interprocedural aliasing in the presence of function pointers. ACAPS Tech. Memo 62, McGill University. December.
• 29: David Paul Grove , Craig Chambers, Effective interprocedural optimization of object-oriented languages, University of Washington, 1998
• 30: Dirk Grunwald , Harini Srinivasan, Data flow equations for explicitly parallel programs, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.159-168, May 19-22, 1993, San Diego, California, United States
• 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: Mary W. Hall , John M. Mellor-Crummey , Alan Carle , René G. Rodríguez, FIAT: A Framework for Interprocedural Analysis and Transfomation, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.522-545, August 12-14, 1993
• 33: Timothy Harris, Early storage reclamation in a tracing garbage collector, ACM SIGPLAN Notices, v.34 n.4, p.46-53, April 1999 [doi>10.1145/312009.312035]
• 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: Nevin Heintze , Olivier Tardieu, Demand-driven pointer analysis, ACM SIGPLAN Notices, v.36 n.5, p.24-34, May 2001
• 36: Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, ACM SIGPLAN Notices, v.36 n.5, p.254-263, May 2001
• 37: Laurie Jane Hendren, Parallelizing programs with recursive data structures, Cornell University, Ithaca, NY, 1990
• 38: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 39: Michael Hind , Anthony Pioli, Which pointer analysis should I use?, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.113-123, August 21-24, 2000, Portland, Oregon, United States
• 40: Martin Hirzel , Amer Diwan , Matthew Hertz, Connectivity-based garbage collection, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 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: Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
• 43: Urs Hölzle , Craig Chambers , David Ungar, Debugging optimized code with dynamic deoptimization, ACM SIGPLAN Notices, v.27 n.7, p.32-43, July 1992
• 44: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, ACM SIGPLAN Notices, v.29 n.6, p.326-336, June 1994
• 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: Thomas Kotzmann , Hanspeter Mössenböck, Escape analysis in the context of dynamic compilation and deoptimization, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064996]
• 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: Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.199-215, September 06-10, 1999, Toulouse, France
• 53: Donglin Liang , Maikel Pennings , Mary Jean Harrold, Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for Java, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.73-79, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379676]
• 54: Donglin Liang , Maikel Pennings , Mary Jean Harrold, Evaluating the precision of static reference analysis using profiling, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 55: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 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: Markus Mock , Manuvir Das , Craig Chambers , Susan J. Eggers, Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-72, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379671]
• 58: Michael Paleczny , Christopher Vick , Cliff Click, The java hotspot^TM server compiler, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.1-1, April 23-24, 2001, Monterey, California
• 59: Igor Pechtchanski , Vivek Sarkar, Dynamic optimistic interprocedural analysis: a framework and an application, ACM SIGPLAN Notices, v.36 n.11, p.195-210, 11/01/2001
• 60: John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, ACM SIGPLAN Notices, v.29 n.10, p.324-340, Oct. 1994
• 61: Feng Qian , Laurie Hendren, Towards dynamic interprocedural analysis in JVMs, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.11-11, May 06-07, 2004, San Jose, California
• 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: Atanas Rountev , Satish Chandra, Off-line variable substitution for scaling points-to analysis, ACM SIGPLAN Notices, v.35 n.5, p.47-56, May 2000
• 64: Atanas Rountev , Ana Milanova , Barbara G. Ryder, Points-to analysis for Java using annotated constraints, ACM SIGPLAN Notices, v.36 n.11, p.43-55, 11/01/2001
• 65: Erik Ruf, Effective synchronization removal for Java, ACM SIGPLAN Notices, v.35 n.5, p.208-218, May 2000
• 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: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Parametric shape analysis via 3-valued logic, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-118, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292552]
• 68: Marc Shapiro, II , Susan Horwitz, The Effects of the Presision of Pointer Analysis, Proceedings of the 4th International Symposium on Static Analysis, p.16-34, September 08-10, 1997
• 69: Vugranam C. Sreedhar , Michael Burke , Jong-Deok Choi, A framework for interprocedural optimization in the presence of dynamic class loading, ACM SIGPLAN Notices, v.35 n.5, p.196-207, May 2000
• 70: Manu Sridharan , Rastislav Bodík, Refinement-based context-sensitive points-to analysis for Java, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 71: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 72: Toshio Suganuma , Toshiaki Yasue , Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, A dynamic optimization framework for a Java just-in-time compiler, ACM SIGPLAN Notices, v.36 n.11, p.180-195, 11/01/2001
• 73: Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, ACM SIGPLAN Notices, v.35 n.10, p.264-280, Oct. 2000
• 74: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, ACM SIGPLAN Notices, v.35 n.10, p.281-293, Oct. 2000
• 75: Raja Vallée-Rai , Etienne Gagnon , Laurie J. Hendren , Patrick Lam , Patrice Pominville , Vijay Sundaresan, Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?, Proceedings of the 9th International Conference on Compiler Construction, p.18-34, March 25-April 02, 2000
• 76: Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, ACM SIGPLAN Notices, v.36 n.5, p.35-46, May 2001
• 77: John Whaley , Monica S. Lam, An Efficient Inclusion-Based Points-To Analysis for Strictly-Typed Languages, Proceedings of the 9th International Symposium on Static Analysis, p.180-195, September 17-20, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages

Keywords:
Pointer analysis, class loading, native interface, reflection