The Generation of Optimal Code for Arithmetic Expressions

ABSTRACT

The problem of evaluating arithmetic expressions on a machine with N ≥ 1 general purpose registers is considered. It is initially assumed that no algebraic laws apply to the operators and operands in the expression. An algorithm for evaluation of expressions under this assumption is proposed, and it is shown to take the shortest possible number of instructions. It is then assumed that certain operators are commutative or both commutative and associative. In this case a procedure is given for finding an expression equivalent to a given one and having the shortest possible evaluation sequence. It is then shown that the algorithms presented here also minimize the number of storage references in the evaluation.

REFERENCES

• 1: 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]
• 2: MEYERS, W .J . Optimization of computer code. Unpublished memorandum, G. E. Research Center, Schenectady, N. Y., 1965 (12 pp.).
• 3: 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]
• 4: Robert W. Floyd, An algorithm for coding efficient arithmetic operations, Communications of the ACM, v.4 n.1, p.42-51, Jan. 1961 [doi>10.1145/366062.366082]
• 5: James P. Anderson, A note on some compiling algorithms, Communications of the ACM, v.7 n.3, p.149-150, March 1964 [doi>10.1145/363958.363976]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

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

General Terms:
Algorithms, Languages, Performance, Theory, Verification