Impact of economics on compiler optimization

ABSTRACT

Compile-time program optimizations are similar to poetry: more are written than are actually published in commercial compilers. Hard economic reality is that many interesting optimizations have too narrow an audience to justify their cost in a general-purpose compiler, and custom compilers are too expensive to write. An alternative is to allow programmers to define their own compile-time optimizations. This has already happened accidentally for C++, albeit imperfectly, in the form of template metaprogramming. This paper surveys the problems, the accidental success, and what directions future research might take to circumvent current economic limitations of monolithic compilers.

REFERENCES

• 1: Angus, I. G. Applications demand class-specific optimizations: The C++ compiler can do more, in Scientific Programming 2,4 (1993), 123-131.
• 2: John Backus, The History of Fortran I, II, and III, IEEE Annals of the History of Computing, v.20 n.4, p.68-78, October 1998 [doi>10.1109/85.728232]
• 3: Bou-Diab, M., Dodgson, M., and Blatter, G. Vortex collisions: crossing or recombination. To appear in Physical Review Letters.
• 4: Shigeru Chiba, A metaobject protocol for C++, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.285-299, October 15-19, 1995, Austin, Texas, United States
• 5: OpenC++ Home Page http://www.hlla.is.tsukuba.ac.jp/-chiba/openc++.html
• 6: Cohn, R., Goodwin, D., Lowney, P.G., and Rubin, N. Spike: An optimizer for Alpha/NT executables. In Proceedings of the USENIX Windows NT Workshop, (Seattle, Washington, Aug. 1997).
• 7: John Lu , Keith D. Cooper, Register promotion in C programs, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.308-319, June 16-18, 1997, Las Vegas, Nevada, United States
• 8: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 9: Julian Dolby , Andrew Chien, An automatic object inlining optimization and its evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.345-357, June 18-21, 2000, Vancouver, British Columbia, Canada
• 10: Dawson R. Engler, Interface Compilation: Steps Toward Compiling Program Interfaces as Languages, IEEE Transactions on Software Engineering, v.25 n.3, p.387-400, May 1999 [doi>10.1109/32.798327]
• 11: Gould, S. J. The Panda's Thumb: More Reflections in Natural History (1980), W. W. Norton & Company, 19-26.
• 12: Samuel Z. Guyer , Calvin Lin, An annotation language for optimizing software libraries, Proceedings of the 2nd conference on Domain-specific languages, p.39-52, October 03-06, 1999, Austin, Texas, United States
• 13: Haney, S., Crotinger, J., Karmesin, S., and Smith, S. PETE: The portable expression template engine. In Dr. Dobb's Journal (October 1999).
• 14: Hastings, R. and Joyce, B. Purify: fast detection of memory leaks and access errors. In Proceedings of Winter 1992 USENIX Conference (San Francisco, CA, 1991), 125-138.
• 15: Intel Pentium 4 Processor Optimization Reference Manual, Chapter 2, (November 2000), Intel Corporation, 7.
• 16: Lamping, J., Kiczales, G., Rodriguez, L.H., and Ruf, Erik. An Architecture for An Open Compiler. In Proceedings of the IMSA '92 Workshop on Reflection and Metu-level Architectures, (Tokyo, Japan, 1992), 95-106.
• 17: Raymond Lo , Fred Chow , Robert Kennedy , Shin-Ming Liu , Peng Tu, Register promotion by sparse partial redundancy elimination of loads and stores, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.26-37, June 17-19, 1998, Montreal, Quebec, Canada
• 18: George C. Necula, Translation validation for an optimizing compiler, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.83-94, June 18-21, 2000, Vancouver, British Columbia, Canada
• 19: Flemming Nielson , Hanne Riis Nielson, Two-level functional languages, Cambridge University Press, New York, NY, 1992
• 20: OpenMP Application Program Interface. http://www.openmp.org
• 21: Arch D. Robison, C++ gets faster for scientific computing, Computers in Physics, v.10 n.5, p.458-462, Sept./Oct. 1996
• 22: Robison, A. D. Method of analyzing definitions and uses in programs with pointers and aggregates in an optimizing compiler. U.S. Patent 5,790,866 (Aug. 4, 1998)
• 23: Robison, A. D. Method of replacing lvalues by variables in programs containing nested aggregates in an optimizing compiler. U.S. Patent 5,710,927 (Jan. 1998).
• 24: A. V. S. Sastry , Roy D. C. Ju, A new algorithm for scalar register promotion based on SSA form, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.15-25, June 17-19, 1998, Montreal, Quebec, Canada
• 25: Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.203-217, June 12-13, 1997, Amsterdam, The Netherlands
• 26: Veldhuizen, T. Expression templates. In C+ + Report 7,5 (June 1995), 26-31.
• 27: Veldhuizen, T. C++ templates as partial evaluation. In Proceedings of the 1999 A CM S1GPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (San Antonio TX, January 1999), ACM Press, 13-18.
• 28: Todd L. Veldhuizen, Just When You Thought Your Little Language Was Safe: ``Expression Templates'' in Java, Proceedings of the Second International Symposium on Generative and Component-Based Software Engineering-Revised Papers, p.188-202, October 09-12, 2000
• 29: Velhuizen, T. Using C++ template metaprograms. In C++ Report 7,4 (May 1995), 36-43.

INDEX TERMS

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

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

General Terms:
Economics, Languages, Performance

Keywords:
compilers, economics, optimization