Code Generation for Machines with Multiregister Operations

Abstract

Previous work on optimal code generation has usually assumed that the underlying machine has identical registers and that all operands fit in a single register or memory location. This paper considers the more realistic problem of generating optimal code for expressions involving single and double length operands, using several models of register-pair machines permitting both single and double word instructions. With register-pair machines a new phenomenom arises that is not present in optimal code generation for single register machines: In an optimal evaluation of an expression it may be necessary to oscillate back and forth between evaluating subexpressions of the expression.A linear-time optimal code generation algorithm is derived for a register-pair machine in which all registers are interchangeable. The algorithm is based on showing that for this model there is an optimal evaluation sequence with limited oscillation between the sub-trees dominated by the children of a given node. For other machine models including the familiar even-odd register-pair machine, optimal evaluation sequences can always require unlimited oscillation.