Efficient Computation of Expressions with Common Subexpressions
Bhaskaram Prabhala, Ravi Sethi · Journal of the ACM · 1980
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.