GoKawiilWelcome 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? That sounds much more promising than non-SSA because the transformation into SSA form has removed (much of) the statefulness of it all. When can we re-use the result?
Identifying instructions that are known at compile-time to always produce the same value at run-time is called value numbering.
Eliminating common subexpressions
... continue reading