Imperative program optimization by partial evaluation

ABSTRACT

We implement strength reduction and loop-invariant code motion by specializing instrumented interpreters; we define a novel program transformation that uses bisimulation to identify and remove code duplication in residual programs; and we discover that some simple classical optimizations, notably constant-propagation, seemingly do not lend themselves to implementation by specialization of instrumented interpreters.

REFERENCES

• 1: Nick Benton, Simple relational correctness proofs for static analyses and program transformations, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-25, January 14-16, 2004, Venice, Italy
• 2: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 3: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 4: R. Glück and J. Jørgensen. Generating optimizing specializers. In IEEE International Conference On Computer Languages, pages 183--194. IEEE Computer Society Press, 1994.
• 5: R. Glück and J. Jørgensen. Generating transformers for deforestation and supercompilation. In B. Le Charlier, editor, Static Analysis, volume 864 of Lecture Notes in Computer Science, pages 432--448. Springer-Verlag, 1994.
• 6: C. K. Gomard and N. D. Jones. Compiler generation by partial evaluation: a case study. Structured Programming, 12:123--144, 1991.
• 7: Neil D. Jones, Transformation by interpreter specialisation, Science of Computer Programming, v.52 n.1-3, p.307-339, August 2004 [doi>10.1016/j.scico.2004.03.010]
• 8: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 9: David Lacey , Neil D. Jones , Eric Van Wyk , Carl Christian Frederiksen, Proving correctness of compiler optimizations by temporal logic, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.283-294, January 16-18, 2002, Portland, Oregon
• 10: Sorin Lerner , Todd Millstein , Craig Chambers, Automatically proving the correctness of compiler optimizations, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 11: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 12: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 13: Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
• 14: Michael Sperber , Peter Thiemann, Realistic compilation by partial evaluation, ACM SIGPLAN Notices, v.31 n.5, p.206-214, May 1996
• 15: Scott Thibault , Charles Consel , Julia L. Lawall , Renaud Marlet , Gilles Muller, Static and Dynamic Program Compilation by Interpreter Specialization, Higher-Order and Symbolic Computation, v.13 n.3, p.161-178, Sept. 2000 [doi>10.1023/A:1010078412711]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Partial evaluation

General Terms:
Experimentation

Keywords:
bisimulation, code duplication, loop-invariant code motion, strength reduction