Optimal code generation for expression trees

ABSTRACT

We discuss the problem of generating code for a wide class of machines, restricting ourselves to the computation of expression trees. After defining a broad class of machines and discussing the properties of optimal programs on these machines, we derive a necessary and sufficient condition which can be used to prove the optimality of any code generation algorithm for expression trees on this class. We then present a dynamic programming algorithm which produces optimal code for any machine in the class; this algorithm runs in time which is linearly proportional to the number of vertices in an expression tree.

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: Aho, A. V., and Ullman, J. D., "Optimization of Straight Line Code," SIAM J. Computing1:1 (1972), 1-19.
• 3: James C. Beatty, An axiomatic approach to code optimization for expressions, Journal of the ACM (JACM), v.19 n.4, p.613-640, Oct. 1972 [doi>10.1145/321724.321728]
• 4: 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]
• 5: Bruno, J., and Sethi, R., "Register Allocation for a One-Register Machine," Technical Report No. 157, Computer Science Dept., Pennsylvania State University, October 3, 1974.
• 6: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 7: Karp, R. M., "Reducibility among Combinatorial Problems," in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, New York (1972), 85-103.
• 8: Knuth, D. E., Fundamental Algorithms, second edition, The Art of Computer Programming 1, Addison-Wesley, Reading, Mass., 1973.
• 9: Ikuo Nakata, On compiling algorithms for arithmetic expressions, Communications of the ACM, v.10 n.8, p.492-494, Aug. 1967 [doi>10.1145/363534.363549]
• 10: R. R. Redziejowski, On arithmetic expressions and trees, Communications of the ACM, v.12 n.2, p.81-84, Feb. 1969 [doi>10.1145/362848.362859]
• 11: Sethi, R., "Complete Register Allocation Problems," Technical Report No. 134, Computer Science Dept., Pennsylvania State University, May, 1974.
• 12: 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]
• 13: Stephen Gibbs Wasilew, A compiler writing system with optimization capabilities for complex object order structures, 1972
• 14: S. A. Walker , H. R. Strong, Characterizations of flowchartable recursions short version, Proceedings of the fourth annual ACM symposium on Theory of computing, p.18-34, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804893]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Theory