Scalable propagation-based call graph construction algorithms

ABSTRACT

Propagation-based call graph construction algorithms have been studied intensively in the 199Os, and differ primarily in the number of sets that are used to approximate run-time values of expressions. In practice, algorithms such as RTA that use a single set for the whole program scale well. The scalability of algorithms such as 0-CFA that use one set per expression remains doubtful.In this paper, we investigate the design space between RTA and 0-CFA. We have implemented various novel algorithms in the context of Jax, an application extractor for Java, and shown that they all scale to a 325,000-line program. A key property of these algorithms is that they do not analyze values on the run-time stack, which makes them efficient and easy to implement. Surprisingly, for detecting unreachable methods, the inexpensive RTA algorithm does almost as well as the seemingly more powerful algorithms. However, for determining call sites with a single target, one of our new algorithms obtains the current best tradeoff between speed and precision.

REFERENCES

• 1: AGESEN, O. Constraint-based type inference and parametric polymorphism. Proceedings of the First International Static Analysis Symposium (SAS'94) (September 1994), 78-100. Springer-Verlag LNCS vol. 864.
• 2: Ole Agesen, Concrete type inference: delivering object-oriented applications, Stanford University, Stanford, CA, 1996
• 3: ANDERSEN, L. O. Self-applicable C program specialization. In Proceedings of PEPM'92, Workshop on Partial Evaluation and Semantics-Based Program Manipulation (June 1992), pp. 54-61. (Technical Report YALEU/DCS/RR-909, Yale University).
• 4: J. Michael Ashley, A practical and flexible flow analysis for higher-order languages, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-194, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237773]
• 5: David Francis Bacon , Susan L. Graham, Fast and effective optimization of statically typed object-oriented languages, 1997
• 6: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 7: Brad Calder , Dirk Grunwald, Reducing indirect function call overhead in C++ programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177973]
• 8: Charles Consel, A tour of Schism: a partial evaluation system for higher-order applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.145-154, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154645]
• 9: DEAN, J., AND CHAMBERS, C. Optimization of object-oriented programs using static class hierarchy analysis. Tech. Rep. 94-12-01, Department of Computer Science, University of Washington at Seattle, December 1994.
• 10: 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
• 11: Greg DeFouw , David Grove , Craig Chambers, Fast interprocedural class analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.222-236, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268965]
• 12: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 13: Manuel Fähndrich , Alexander Aiken, Program Analysis Using Mixed Term and Set Constraints, Proceedings of the 4th International Symposium on Static Analysis, p.114-126, September 08-10, 1997
• 14: Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su , Alexander Aiken, Partial online cycle elimination in inclusion constraint graphs, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.85-96, June 17-19, 1998, Montreal, Quebec, Canada
• 15: Jeffrey S. Foster , Manuel Fähndrich , Alexander Aiken, Polymorphic versus Monomorphic Flow-Insensitive Points-to Analysis for C, Proceedings of the 7th International Symposium on Static Analysis, p.175-198, June 29-July 01, 2000
• 16: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 17: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 18: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 19: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 20: Fritz Henglein, Dynamic typing, Symposium proceedings on 4th European symposium on programming, p.233-253, January 1992, Rennes, France
• 21: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Hideaki Komatsu , Toshio Nakatani, A study of devirtualization techniques for a Java Just-In-Time compiler, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.294-310, October 2000, Minneapolis, Minnesota, United States
• 22: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Mikio Takeuchi , Takeshi Ogasawara , Toshio Suganuma , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Design, implementation, and evaluation of optimizations in a just-in-time compiler, Proceedings of the ACM 1999 conference on Java Grande, p.119-128, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304111]
• 23: Suresh Jagannathan , Stephen Weeks, A unified treatment of flow analysis in higher-order languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.393-407, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199536]
• 24: Suresh Jagannathan , Andrew K. Wright, Effective Flow Analysis for Avoiding Run-Time Checks, Proceedings of the Second International Symposium on Static Analysis, p.207-224, September 25-27, 1995
• 25: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• 26: Flemming Nielson , Hanne Riis Nielson, Infinitary control flow analysis: a collecting semantics for closure analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.332-345, January 15-17, 1997, Paris, France [doi>10.1145/263699.263745]
• 27: Nicholas Oxhøj , Jens Palsberg , Michael I. Schwartzbach, Making Type Inference Practical, Proceedings of the European Conference on Object-Oriented Programming, p.329-349, June 29-July 03, 1992
• 28: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type systems, John Wiley and Sons Ltd., Chichester, UK, 1994
• 29: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
• 30: David A. Schmidt, Natural-Semantics-Based Abstract Interpretation (Preliminary Version), Proceedings of the Second International Symposium on Static Analysis, p.1-18, September 25-27, 1995
• 31: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 32: SHARIR, M., AND PNUELI, A. Two approaches to interprocedural data flow analysis. In Program Flow Analysis, Theory and Applications, S. Muchnick and N. Jones, Eds. 1981.
• 33: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 34: Amitabh Srivastava, Unreachable procedures in object-oriented programming, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.355-364, Dec. 1992 [doi>10.1145/161494.161517]
• 35: 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]
• 36: Dan Stefanescu , Yuli Zhou, An equational framework for the flow analysis of higher order functional programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.318-327, June 27-29, 1994, Orlando, Florida, United States
• 37: Zhendong Su , Manuel Fähndrich , Alexander Aiken, Projection merging: reducing redundancies in inclusion constraint graphs, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-95, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325706]
• 38: Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.264-280, October 2000, Minneapolis, Minnesota, United States
• 39: Peter F. Sweeney , Frank Tip, Extracting library-based object-oriented applications, Proceedings of the 8th ACM SIGSOFT international symposium on Foundations of software engineering: twenty-first century applications, p.98-107, November 06-10, 2000, San Diego, California, United States
• 40: Frank Tip , Chris Laffra , Peter F. Sweeney , David Streeter, Practical experience with an application extractor for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, November 01-05, 1999, Denver, Colorado, United States
• 41: 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
• 42: Jan Vitek , R. Nigel Horspool , Andreas Krall, Efficient type inclusion tests, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.142-157, October 05-09, 1997, Atlanta, Georgia, United States

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Standardization, Theory