Previous results have shown that it ~s easy to generate optimal code from express,on trees, and that optimal code generauon becomes very difficult ff arbitrary common subexpress,ons are handled In this paper a class of expressions containing restricted common subexpressions from which optimal code can be generated effictentty is studied.These expressions are represented by a class of series-parallel graphs, which the authors call collapsible graphs, that mchide trees and are general enough to permit large common subexpresslons, but from which optmml code can be generated m polynomml time for a class of stack machines KEY WORDS AND PHRASES" reg,ster allocaUon, code generation, polynomml algorithm, series-parallel graphs, common subexpresslons, stack machines CR CATEGORIES. 4 12, 5.25 15, lq.Elaborating on (b) above, Bruno and Sethi [11] show that the problem of generating optimal code for a one-register machine is NP-complete.Aho et al. [5] add that even when all common subexpressions have exactly one operaUon, optimal code generation is NPcomplete for a one-register machine and also for an infinite-register machine. 1 Since the stack machines we consider are a generalization of one-register machines, the NP-completeness results from [5, 11] carry-over to stack machines.

Suppose you are approached by a computer designer who wants to select a machine architecture and instruction set that is desirable from a compiler writers standpoint. What would you recommend, and why? We give a limited answer to the above question. We focus on the computation of arithmetic expressions like a−b+c. When computing a−b we need different instructions depending on where a and b are to be found. On a programmable calculator for example, a or b may be on the stack, or stored in some memory register. We also need instructions that copy values from one place to another. Algorithms that generate code for arithmetic expressions tend to treat general purpose registers as a stack. Moreover, results about machines that perform all arithmetic in a hardware stack are directly applicable to machines with general purpose registers. We therefore start our study of instruction sets by looking at stack machines. We compare machines based on the number of instructions needed to compute a given expression. We then turn to algorithms that generate optimal programs for computing expressions on the various machines.