Call forwarding: a simple interprocedural optimization technique for dynamically typed languages

ABSTRACT

This paper discusses call forwarding, a simple interprocedural optimization technique for dynamically typed languages. The basic idea behind the optimization is straightforward: find an ordering for the “entry actions” of a procedure, and generate multiple entry points for the procedure, so as to maximize the savings realized from different call sites bypassing different sets of entry actions. We show that the problem of computing optimal solutions to arbitrary call forwarding problems is NP-complete, and describe an efficient greedy algorithm for the problem. Experimental results indicate that (i) this algorithm is effective, in that the solutions produced are generally close to optimal; and (ii) the resulting optimization leads to significant performance improvements for a number of benchmarks tested.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 4: M. Carlsson and J. Widen, SICStus Prolog User's Manual, Swedish Institute of Computer Science, Oct. 1988.
• 5: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, ACM SIGPLAN Notices, v.25 n.6, p.150-164, Jun. 1990
• 6: C. Chambers , D. Ungar , E. Lee, An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes, Conference proceedings on Object-oriented programming systems, languages and applications, p.49-70, October 02-06, 1989, New Orleans, Louisiana, United States
• 7: Saumya K. Debray, A simple code improvement scheme for Prolog, Journal of Logic Programming, v.13 n.1, p.57-88, May 1992 [doi>10.1016/0743-1066(92)90021-T]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: M. R. Garey, D. S. Johnson, and L. Stockmeyer, "Some Simplified NP-complete Graph Problems", Theoretical Computer Science vol. 1, pp. 237-267, 1976.
• 10: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 11: D. Gudeman, K. De Bosschere, and S. K. Debray, "jc : An Efficient and Portable Implementation of Janus", Proc. Joint International Conference and Symposium on Logic Programming, Washington DC, Nov. 1992. MIT Press.
• 12: A. Mari~n, G. janssens, A. Mulkers, and M. Bruynooghe, "The Impact of Abstract Interpretation: An Experiment in Code Generation", Proc. Sixth International Conference on Logic Programming, Lisbon, June 1989, pp. 33-47. MIT Press.
• 13: Vijay A. Saraswat , Ken Kahn , Jacob Levy, Janus: a step towards distributed constraint programming, Proceedings of the 1990 North American conference on Logic programming, p.431-446, January 1990, Austin, Texas, United States
• 14: J. T. Schwartz , R. B. Dewar , E. Schonberg , E. Dubinsky, Programming with sets; an introduction to SETL, Springer-Verlag New York, Inc., New York, NY, 1986
• 15: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 16: A. Taylor, "Removal of Dereferencing and Trailing in Prolog Compilation", Proc. Sixth International Conference on Logic Programming, Lisbon, June 1989, pp. 48-60. MIT Press.
• 17: K. Ueda, Guarded horn clauses, Concurrent Prolog, MIT Press, Cambridge, MA, 1988
• 18: Peter Lodewijk Van Roy, Can logic programming execute as fast as imperative programming?, University of California at Berkeley, Berkeley, CA, 1991
• 19: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

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

General Terms:
Algorithms, Measurement, Performance, Theory, Verification