Common Subexpression Elimination

KISS

Keep it simple stupid

What we think of as intuitive optimization (except not really).
Here, we eliminate common sub-expressions by only computing them one, and setting identical computations equivalent to the earlier computation.

From Three Address Code

s = x+y
t = k+n
a = s+t
u = x+y
v = k+n
b = u*v

After CSE…

s=x+y
t=K=n
a=s+t
u=s
v=t
v=u*v

Uses Available Expressions when we do it with equations.

• Examine each statement and see if the expression it evaluates is already available $In\bigcap Gen$ is non-empty. Then set that line to the precomputed variable.

We may need to do this with loops and branches.