Optimizations for expression programs

Optimizations for expression programs#

Despite its simplicity, the language of Expression Programs is sufficiently interesting to exemplify a number of standard optimizations, listed in this section. Each is a rewriting of the program that preserves the value it returns. The implementation of some of these optimizations is described in Implementation of basic optimizations.

The examples use the source syntax of the assignment: val, input, and a final return.

Constant folding#

An operation whose operands are both constants, and that can be done statically at compile time, is replaced by its result.

Before:

val x = 2 + 2
return x

After:

val x = 4
return x

Algebraic simplification#

An operation is rewritten using an algebraic law, so that it disappears or becomes cheaper. The operands need not be constants.

Before:

input x
val y = x * 1
val z = y - y
return y + z

After:

input x
val y = x
val z = 0
return y + z

Constant propagation#

A variable bound to a constant is replaced by that constant where it is used.

Before:

val x = 2
val y = 2 + x
return y

After:

val x = 2
val y = 2 + 2
return y

Copy propagation#

A variable bound to another variable is replaced by that variable where it is used.

Before:

input x
val y = x
return y

After:

input x
val y = x
return x

Common subexpression elimination (CSE)#

An expression that is computed more than once is computed once, bound to a fresh variable, and the variable is used in its place.

Before:

input x
val y = x * x + x * x
return y

After:

input x
val t = x * x
val y = t + t
return y

Dead code elimination (DCE)#

A binding whose variable is not used by any later statement or by the returned expression is removed.

Before:

input x
val y = x * x
return 0

After:

input x
return 0

Note that an input statement is not removed, even when its variable is unused: in this language, the input is a side effect, and removing the statement would change what the program consumes.

Strength reduction#

An expensive operation is replaced by a cheaper one with the same result.

  • a * 4 → a << 2

  • a * 7 → (a << 3) - a

Which operations are cheaper depends on the target architecture. Note that our expression language has no shift operators, so these rewritings cannot be expressed in it right now; if it had them, this optimization would apply in the same way as the others.

Combining the optimizations#

One optimization exposes opportunities for another: folding produces constants for propagation, and propagation leaves behind unused bindings for DCE. The optimizations are therefore applied repeatedly until the program stops changing; see the driver in Implementation of basic optimizations.

Contents