An intermediate language for source and target independent code optimization

ABSTRACT

This paper describes an intermediate language to be generated by a syntax analyzer and processed by a code generator. An (essentially) optional code optimization phase may be used before code generation. The language is designed to exclude source and target dependencies (these are specified in a set of auxiliary tables) and has been used to implement a general purpose code optimization module. This module has been incorporated into compilers for several source languages and has resulted in production-quality target code. The paper focuses on the features of the language and reviews the optimizations for which it has been designed. A major benefit of this approach has been to isolate many of the characteristics which lead to code optimization opportunities. Of particular note are numerous facts which can be gathered in a target-independent manner, even though their utilization will depend on the details of the target machine.

REFERENCES

• 1: Allen, Frances E., "Program Optimization" in Annual Review in Automatic Programming, ed. Mark I. Halpern and Christopher J. Shaw. Vol. V. Oxford: Pergamon Press, 1969, 239-307.
• 2: John T. Bagwell, Jr., Local optimizations, Proceedings of a symposium on Compiler optimization, p.52-66, July 27-28, 1970, Urbana-Champaign, Illinois
• 3: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 4: Earnest, C. P., "Some Topics in Code Optimization," Computer Sciences Corporation, 1969.
• 5: Dennis J. Frailey, Expression optimization using unary complement operators, Proceedings of a symposium on Compiler optimization, p.67-85, July 27-28, 1970, Urbana-Champaign, Illinois
• 6: Dennis John Frailey, A study of code optimization using a general purpose optimizer, 1971
• 7: Halstead, Maurice, "Machine Independence and Third Generation Computers" in Proceedings of the Fall Joint Computer Conference. Washington: Thompson Books, 1967, 587-592.
• 8: Neal Laurance, A compiler language for data structures, Proceedings of the 1968 23rd ACM national conference, p.387-394, August 27-29, 1968 [doi>10.1145/800186.810603]
• 9: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 10: Sam F. Mendicino , Robert A. Hughes , Jeanne T. Martin , Frank H. McMahon , John E. Ranelletti , Richard G. Zwakenberg, The LRLTRAN compiler, Communications of the ACM, v.11 n.11, p.747-755, Nov. 68 [doi>10.1145/364139.364154]
• 11: Rustin, Randall (ed.), Design and Optimization of Compilers. Englewood Cliffs, N. J.: Prentice Hall, 1972.
• 12: Tarjan, Robert E., "Complexity of Combinatorial Algorithms," SIAM Review, XX (July, 1978), 457-491.

INDEX TERMS

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

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

General Terms:
Languages