Adapting Optimal Code Generation for Arithmetic Expressions to the Instruction Sets Available on...

This article refers to another article that was published in the October 1970 issue of the "Journal of the ACM," which discussed the generation of optimal code. A restriction was imposed on the commands allowing register-register operation. However, allowing the result of a register-register operation to be placed into any register makes their results irrelevant, since such generality is not available in most present day machines. Instead, most present day machines place the result in the register containing the first operand. A new algorithm produces code in the same manner as the old one, with the same number of registers available at each node of the tree. The novelty of this algorithm is that it uses indirect register specification. As a result, the registers can be ordered to fit the instruction set of present day machines. The old algorithm was accompanied by proofs of its correctness and optimality. These proofs are still valid for the improved algorithm since the new algorithm does not violate any of the hypotheses of those proofs.