# Optimizations for expression programs
(eprog-opt)=

Despite its simplicity, the language of [Expression
Programs](assignment-2) 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](basic-opt.md).

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:

```text
val x = 2 + 2
return x
```

After:

```text
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:

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

After:

```text
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:

```text
val x = 2
val y = 2 + x
return y
```

After:

```text
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:

```text
input x
val y = x
return y
```

After:

```text
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:

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

After:

```text
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:

```text
input x
val y = x * x
return 0
```

After:

```text
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](basic-opt.md).