Instruction Sets for Evaluating Arithmetic Expressions

The evaluation of anthmeuc expressions on both register-oriented and stack-oriented machines can be studied using the same model because registers can be treated as a stack during the evaluation of expression trees, without loss m code efficiency The machine model in this paper has a hardware stack m which all computatmns take place. Register-regmer and regmer-memory instructions are modeled by considering four possible instrucuons for each binary operator, depending on whether one or two operands are taken from the stack and on whether the left or the right operand is on top of the stack. There is a cost assocJated wtth each operation code, as well as costs for accessing a value in a register or in memory. The mtmmum cost of computing an expression tree is used to compare machines. The comparisons fall into two classes (1) By keeping the instruction set fixed, the effect of increasing the number of registers is studied. (2) Various machines are compared with a machine that has all four kinds of operation instructmns and an arbitrarily deep stack. As part of the framework that allows the comparisons to be performed, a parametenzed algonthm for determining the number of stores that must occur in an optimal computation is developed This algorithm forms the basis of an opttmal code generation algorithm.