Generalized common subexpressions in very high level languages

Abstract

We propose a new optimization technique applicable to set-oriented languages, which we shall call general common subexpression elimination. It involves the computation of the IAVAIL(n) function for all nodes n in a flow graph, where IAVAIL(n) is the set of expressions such that along every path leading to n, there will be found a computation of the expression followed by only incidental assignments (i.e. A = A ∪ {x} or A = A - {x}) to its operands and that the number of such assignments is bounded, independent of the path taken. We shall try to justify our definitions and demonstrate the usefulness of this technique by several examples. We shall show that this optimization problem does not fit into the semilattice-theoretic model for global program optimization [Ki, KU, GW], and that the standard iterative algorithm for such problems does not work in this case. We then give several theorems which allow the problem to be solved for reducible flow graphs. The formulae given in the theorems are in such a form that an efficient algorithm can be found by adapting an algorithm given in [U]. The resulting algorithm takes 0(e log e) steps of an extended type, where bit vector operations are regarded as one step, and e is the number of edges of the flow graph. It takes 0(n log n) extended steps for a program flow graph of n nodes.