Welcome back to compiler land. Today we’re going to talk about value numbering , which is like SSA, but more.

Static single assignment (SSA) gives names to values: every expression has a name, and each name corresponds to exactly one expression. It transforms programs like this:

x = 0 x = x + 1 x = x + 1

where the variable x is assigned more than once in the program text, into programs like this:

v0 = 0 v1 = v0 + 1 v2 = v1 + 1

where each assignment to x has been replaced with an assignment to a new fresh name.

It’s great because it makes clear the differences between the two x + 1 expressions. Though they textually look similar, they compute different values. The first computes 1 and the second computes 2. In this example, it is not possible to substitute in a variable and re-use the value of x + 1 , because the x s are different.

But what if we see two “textually” identical instructions in SSA?…