Local Optimization

Some statements can be deleted

x := x + 0
x := x * 1
Eliminating these instructions are great optimizations as we are removing an entire instruction.

Some statements can be simplified

x := x * 0  =>  x := 0
Maybe the instruction on the right is faster than the instruction on the right. More importantly, assigning to a constant allows more cascading optimizations, as we will see later.

Another example:

y := y ** 2  => y := y * y
Typically, an architecture will not have the exponentiation instruction and so this operator may have to be implemented by an exponentiation loop in software. For the special cases (e.g., exponent = 2), we can simply replace by multiplication.

Another example:

x := x * 8  => x := x << 3
x := x * 15  => t := x << 4; x := t - x
Replace multiplication by a power-of-two to a shift-left operation. Can also do this for non powers-of-two. On some machines, left-shift is faster than multiply, but not on all! Modern machines have their own "rewriting logic" in hardware that can deal with these special cases really fast. In other words, some of these compiler local optimizations may become less relevant on modern hardware.

All these transformations are examples of algebraic simplifications.

Operations on constants can be computed at compile time

Examples

This class of optimizations is called constant folding. One of the most consequential and most common optimizations performed by compilers.

Another important optimization: eliminate unreachable basic blocks (dead code):

Called dead-code elimination.

Why would unreachable basic blocks occur?

Some optimizations are simplified if each register occurs only once on the left-hand side of an assignment.

More complicated in general, due to loops

If

Then Example
x := y + z
....
....
w := y + z
We can be sure that the values of x, y, and z do not change in the code. Hence, we can replace the assignment to w as follows:
x := y + z
....
....
w := x
This optimization is called common-subexpression elimination. This is also another very common and consequential compiler optimization.

If we see w := x appears in a block, replace subsequent uses of w with uses of x

Example:
b := z + y
a := b
x := 2 * a
This can be replaced with
b := z + y
a := b
x := 2 * b
This is called copy propagation. This is useful for enabling other optimizations

Example:

a := 5
x := 2 * a
y := x + 6
t := x * y
gets transformed to
a := 5
x := 10
y := 16
t := x >> 4
We could have also assigned 160 to t. That would be even better.

If w := rhs appears in a basic block and w does not appear anywhere else in the program, THEN the statement w := rhs is dead and can be eliminated.

In our copy-propagation example, one of the assignments is dead and can be eliminated.

Why Static Single Assignment (SSA)?

Converting to SSA

Show two acyclic examples: one straight-line and one with a diamond structure.

The need for phi nodes: show a diamond structure where two different versions of the same variable reach the same point. Define y3=phi(y1,y2) at the beginning of the meet point.

Inserting PHI nodes: Path convergence criterion: need Phi node for a variable a at node z iff:

Example

a := x ** 2
b := 3
c := x
d := c * c
e := b * 2
f := a + d
g := e + f

Final form

a := x * x
f := a + a
g := 6 * f
Possible to simplify further, but the compiler may get stuck in "local minima". e.g., should it have changed a + a to 2 * a, it would have had a better optimization opportunity (replacing g = 12*f and eliminating computation of f).

Peephole optimization

Peephole optimizations are usually written as replacement rules

i1; i2; i3; ..; in --> j1; j2; ..; jm
Example:
move $a $b; move $b $a --> move $a $b
Works if the second instruction is not the target of a jump (i.e., both instructions belong to a basic block).

Another example:

addiu $a $a i; addiu $a $a j --> addiu $a $a (i+j)

Many (but not all) of the basic block optimizations can be cast as peephole optimizations

As for local optimizations, peephole optimizations must be applied repeatedly for maximum effect

Many simple optimizations can still be applied on assembly language.

"Program optimiztion" is grossly misnamed