Code generation for expressions with common subexpressions (Extended Abstract)

ABSTRACT

Easy as the task may seem, many compilers generate rather inefficient code. Some of the difficulty of generating good code may arise from the lack of realistic models for programming language and machine semantics. In this paper we show that the computational complexity of generating efficient code in realistic situations may also be a major cause of difficulty in the design of good compilers. We consider the problem of generating optimal code for a set of expressions. If the set of expressions has no common sub-expressions, then a number of efficient optimal code generation algorithms are known for wide classes of machines [SU, AJ, BL].

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: A. V. Aho , S. C. Johnson, Optimal code generation for expression trees, Proceedings of seventh annual ACM symposium on Theory of computing, p.207-217, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803770]
• 3: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 4: J. C. Beatty, "A Register Assignment Algorithm for Generation of Highly Optimised Object Code," IBM J. Res. Dev. 18,1 (January 1974), 20-39.
• 5: L. A. Belady, "A Study of Replacement Algorithms for Virtual Storage Computers," IBM Syst. J., 5:2 (1966) 78-101.
• 6: Melvin A. Breuer, Generation of optimal code for expressions via factorization, Communications of the ACM, v.12 n.6, p.333-340, June 1969 [doi>10.1145/363011.363153]
• 7: J. L. Bruno , T. Lassagne, The Generation of Optimal Code for Stack Machines, Journal of the ACM (JACM), v.22 n.3, p.382-396, July 1975 [doi>10.1145/321892.321901]
• 8: J. L. Bruno and R. Sethi, "Register Allocation for a One-Register Machine," TR-157, Computer Science Dept., Penn State Univ., University Park, Pa., Oct., 1974.
• 9: S. Chen, "On the Sethi-Ullman Algoport #11, Bell Laboratories, Holmdel, N. J., May, 1973.
• 10: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 11: A. Demers, private communication.
• 12: Richard J. Fateman, Optimal code for serial and parallel computation, Communications of the ACM, v.12 n.12, p.694-695, Dec. 1969 [doi>10.1145/363626.363661]
• 13: R. A. Freiburghouse, Register allocation via usage counts, Communications of the ACM, v.17 n.11, p.638-642, Nov. 1974 [doi>10.1145/361179.361201]
• 14: L. P. Horwitz , R. M. Karp , R. E. Miller , S. Winograd, Index Register Allocation, Journal of the ACM (JACM), v.13 n.1, p.43-61, Jan. 1966 [doi>10.1145/321312.321317]
• 15: R. Sethi, "Complete Register Allocation Problems," SIAM J. Computing 4,3 (September 1975), 226-248.
• 16: R. Sethi, private communication.
• 17: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
• 18: William M. Waite, Optimization, Compiler Construction, An Advanced Course, 2nd ed., p.549-602, January 1976
• 19: Stephen Gibbs Wasilew, A compiler writing system with optimization capabilities for complex object order structures, 1972
• 20: 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

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Algorithms, Languages, Performance, Theory