Towards automatic construction of staged compilers

ABSTRACT

Some compilation systems, such as offline partial evaluators and selective dynamic compilation systems, support staged optimizations. A staged optimization is one where a logically single optimization is broken up into stages, with the early stage(s) performing preplanning set-up work, given any available partial knowledge about the program to be compiled, and the final stage completing the optimization. The final stage can be much faster than the original optimization by having much of its work performed by the early stages. A key limitation of current staged optimizers is that they are written by hand, sometimes in an ad hoc manner. We have developed a framework called the Staged Compilation Framework (SCF) for systematically and automatically converting single-stage optimizations into staged versions. The framework is based on a combination of aggressive partial evaluation and dead-assignment elimination. We have implemented SCF in Standard ML. A preliminary evaluation shows that SCF can speed up classical optimization of some commonly used C functions by up to 12× (and typically between 4.5× and 5.5×).

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Alex Aiken , Brian Murphy, Static type inference in a dynamically typed language, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.279-290, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99621]
• 3: Alexander Aiken , Brian R. Murphy, Implementing regular tree expressions, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.427-447, June 1991, Cambridge, Massachusetts, United States
• 4: Alexander Aiken , Brian R. Murphy, Implementing regular tree expressions, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.427-447, June 1991, Cambridge, Massachusetts, United States
• 5: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 6: C. Chambers, J. Dean, and D. Grove. Whole-program optimization of objectoriented languages. Technical Report TR-96-06-02, Department of Computer Science and Engineering. University of Washington, June 1996.
• 7: C. Consel , O. Danvy, From interpreting to compiling binding times, Proceedings of the third European symposium on programming on ESOP '90, p.88-105, May 1990, Copenhagen, Denmark
• 8: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 9: Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
• 10: Amer Diwan , J. Eliot B. Moss , Kathryn S. McKinley, Simple and effective analysis of statically-typed object-oriented programs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, October 06-10, 1996, San Jose, California, United States
• 11: Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.103-115, June 18-21, 1995, La Jolla, California, United States
• 12: Robert Fitzgerald , Todd B. Knoblock , Erik Ruf , Bjarne Steensgaard , David Tarditi, Marmot: an optimizing compiler for Java, Software—Practice & Experience, v.30 n.3, p.199-232, Mar.1.2000 [doi>10.1002/(SICI)1097-024X(200003)30:3<199::AID-SPE296>3.0.CO;2-2]
• 13: Robert Glück , Jesper Jørgensen, An Automatic Program Generator for Multi-Level Specialization, Lisp and Symbolic Computation, v.10 n.2, p.113-158, July 1997 [doi>10.1023/A:1007763000430]
• 14: Brian Grant , Markus Mock , Matthai Philipose , Craig Chambers , Susan J. Eggers, Annotation-directed run-time specialization in C, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.163-178, June 12-13, 1997, Amsterdam, The Netherlands
• 15: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, An evaluation of staged run-time optimizations in DyC, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.293-304, May 01-04, 1999, Atlanta, Georgia, United States
• 16: 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
• 17: 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
• 18: Carsten Kehler Holst, Finiteness analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.473-495, June 1991, Cambridge, Massachusetts, United States
• 19: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 20: Neil D. Jones , Steven S. Muchnick, Flow analysis and optimization of LISP-like structures, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.244-256, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567776]
• 21: M. Leone and P. Lee. Optimizing ML with run-time code generation. Technical report CMU-CS-95-205, School of Computer Science, Carnegie Mellon University, December 1995.
• 22: Yanhong A. Liu , Scott D. Stoller, Eliminating Dead Code on Recursive Data, Proceedings of the 6th International Symposium on Static Analysis, p.211-231, September 22-24, 1999
• 23: Renaud Marlet , Charles Consel , Philippe Boinot, Efficient incremental run-time specialization for free, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.281-292, May 01-04, 1999, Atlanta, Georgia, United States
• 24: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 25: Francois Noel , Luke Hornof , Charles Consel , Julia L. Lawall, Automatic, Template-Based Run-Time Specialization: Implementation and Experimental Study, Proceedings of the 1998 International Conference on Computer Languages, p.132, May 14-16, 1998
• 26: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 27: Thomas W. Reps , Todd Turnidge, Program Specialization via Program Slicing, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.409-429, February 12-16, 1996
• 28: J. C. Reynolds. Automatic computation of data set definitions. In A. J. H. Morrell, editor, Information Processing 68, volume 1, pages 456-461, Amsterdam, 1969. North-Holland.
• 29: Erik Steven Ruf, Topics in online partial evaluation, Stanford University, Stanford, CA, 1993
• 30: Michael Sperber , Peter Thiemann, Two for the price of one: composing partial evaluation and compilation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.215-225, June 16-18, 1997, Las Vegas, Nevada, United States
• 31: 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
• 32: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990
• 33: Daniel Weise , Roland Conybeare , Erik Ruf , Scott Seligman, Automatic online partial evaluation, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.165-191, June 1991, Cambridge, Massachusetts, United States