Compiler design for efficient code generation and program optimization

ABSTRACT

This paper describes the design of a compiler for an extended PASCAL with particular emphasis on code generation and optimization. The design objectives are: compiler reliability, code generator portability and object code efficiency. Designing a compiler to meet the above objectives usually requires compromises in the design. To achieve the objective of compiler reliability, one frequently tries to simplify the compiler design in order to reduce the complexity that must be mastered in the implementation. Unfortunately, the objective of producing efficient code conflicts with the objective of simplifying the compiler design. The design presented in this paper attempts to maximize the attainment of these objectives with minimal compromises.

REFERENCES

• 1: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 2: Allen, F.E. Program optimization. Ann. Rev. Automatic Programming. 5 (1979), pp. 239-307.
• 3: Allen, F.E. Interprocedural data flow analysis. Information Processing 74, North-Holland Pub. Co., Amsterdam. (1974), pp. 398-402.
• 4: Allen, F.E. et al. The experimental compiling systems project. IBM Research report, RC 6718 (#28922) (June 1977).
• 5: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 6: J. Lawrence Carter, A case study of a new code generation technique for compilers, Communications of the ACM, v.20 n.12, p.914-920, Dec. 1977 [doi>10.1145/359897.359902]
• 7: John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
• 8: John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
• 9: Christopher W. Fraser, A compact, machine-independent peephole optimizer, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-6, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567753]
• 10: R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512785]
• 11: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 12: Hecht, M.S., and Ullman, J.D. A simple algorithm for global data flow analysis problems. SIAM J. 4 (1975), pp. 519-532.
• 13: K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
• 14: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 15: Knuth, D.E. An empirical study of FORTRAN programs. Software - Practice and Experience 1,2 (April-June 1971), pp. 105-133.
• 16: David B. Loveman, Program improvement by source to source transformation, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.140-152, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811548]
• 17: Barry K. Rosen, High-level data flow analysis, Communications of the ACM, v.20 n.10, p.712-724, Oct. 1977 [doi>10.1145/359842.359849]
• 18: Andres Rudmik, On the generation of optimizing compilers., 1975
• 19: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 20: Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977 [doi>10.1145/359810.359830]
• 21: Schneck, P.B., and Angel, E. A FORTRAN to FORTRAN optimising compiler. Computer J. 16 (1973), pp. 322-330.
• 22: Thomas G. Szymanski, Assembling code for machines with span-dependent instructions, Communications of the ACM, v.21 n.4, p.300-308, April 1978 [doi>10.1145/359460.359474]
• 23: Ullman, J.D. Data flow analysis. Second USA-Japan Computer. Conf., (1975), pp. 335-342.
• 24: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975
• 25: Zelkowitz, M.V., and Bail, W.G. Optimization of structured programs, Software and Practice 4 (1974), pp. 51-57.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Portability
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Languages, Reliability