The Generation of Optimal Code for Arithmetic Expressions

TLDR

The paper addresses evaluating arithmetic expressions on machines with at least one general‑purpose register. The authors propose an algorithm that achieves the shortest possible instruction count for evaluating expressions. The study first assumes no algebraic laws, then considers commutative or associative operators, and provides a procedure to find an equivalent expression with the shortest evaluation sequence. The algorithm achieves minimal instruction count and also minimizes storage references during evaluation.

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.